Input Size as Bits

Below is a scan of the paper that Dr. Sugihara went over with me. In the top right is a box representing a function that performs a calculation on an integer as input (e.g., 8). In this case, it's misleading to think that Big-Oh is O(n) because n=1. Rather, you must consider n as the number of bits necessary to represent the value of the integer. This can be found by getting the ceiling function of log2(r+1) (log base 2 of (r+1), where r is the value of the integer). Thus, you can say that the function is O(2^log2r). (I believe this is because for n number of bits, the maximum number of distinct integer values that can be represented is 2^n. So, this would be dealing with worst case complexity.) You can then say that the function has a time complexity of O(2^n), since n is the number of bits required for the input integer. (Please read the preceding paragraph >= 3 times and study the successive scanned scribbles to make sense of any of this.)

Back to 311 page

last modified: 02/11/00