def function(N):
foo = 1
while foo < N:
foo *= 2
return foo
I think it's O(log N), since foo is being multiplied by a constant amount?
Asked
Active
Viewed 217 times
-1
Pig
- 2,002
- 5
- 26
- 42
-
2You are correct. – Andreas Jun 21 '20 at 08:19
-
O(N*loglogN) -- right shift 32 bits, check for 0, then by 16, then 8, etc. – Rick James Jun 23 '20 at 18:46
-
O(1) -- Convert to float, then play with the exponent. (That is, let that conversion do a "normalize" to discover number of leading 0s.) – Rick James Jun 23 '20 at 18:47
1 Answers
1
This is something you can easily show by the definition of logarithm. For simplicity we consider base 2 logarithm (all log bases are equivalent in big-O notation since they are all within a constant factor of each other).
log2 n = k
means:
2 ** k = n
but 2 ** k is actually 2 * 2 * 2 ... * 2 (k times) -- for integer k.
For any given n, k may not be integer, but you can safely consider the next positive integer k as that guarantees that 2 ** k is larger than n.
So, the number of * 2 operation needed to go from 1 to n is k (within unity).
norok2
- 25,683
- 4
- 73
- 99