"Big O" of this power-of-2 function

Question

What is the "Big O" of the following function? My assumption is that it is O(log(n)) but I would like to double check. The function simply determines if its argument is a power of 2.

def pow_of_2(x):
    a = math.log(x, 2)
    if a == math.floor(a):
       return True
    else:
       return False

This appears to be `O(1)` because it does a fixed calculation and then returns either `True` or `False`. — Tim Biegeleisen, Jan 19 '16 at 05:16
but isn't the calculation a variable based on x @TimBiegeleisen — user3121369, Jan 19 '16 at 05:19
The function is O(log(x)) (because converting x to a double is O(log x)), but also produces wrong results for large x. For example, `pow_of_2(2 ** 1000)` returns False. — Paul Hankin, Jan 19 '16 at 05:19
I think you are confused about running time analysis. The function simply compute a log and then returns. This is a constant penalty. If you had a loop, or another type of structure, then the running time would not be constant. — Tim Biegeleisen, Jan 19 '16 at 05:20
I'm with Tim. O(1). It doesn't make sense for it to be anything else since there is nothing in the problem to be "n". There's a single scalar variable (`x`), and you only do a fixed number of operations with it (no matter what value "x" has). — mgilson, Jan 19 '16 at 05:48
I suspect that the OP is asking about the complexity in terms of x, ie how would doubling x affect the time for the function to return. This is impossible to answer without knowing exactly how the math library computes the log function. It is generally the case, however, that a larger x will increase the time, but as x grows that penalty will shrink. It is certainly not as bad as O(x), but definitely worse than O(1). I would suspect that the O(log(x)) is probably close. Running the function many times for large x, suggests that the time is proportional to log(x) asymptotically. — Matthew, Jan 19 '16 at 06:16

score 5 · Answer 1 · edited May 23 '17 at 12:01

The Big-O of the function is not constant time.

The Big-O of the function will be the same as the Big-O of the function math.log. This basically depends on the implementation of the function. (The math.floor function can be implemented in constant time).

The log function is typically computed using the Taylor-series expansion and is O(M(n) * n^0.5) where M(n) is the complexity of multiplying two n-digit numbers.

For more information on this, please look at this link.

Note: If you want to check if a number is a power of 2, all you need to do is the following check with binary arithmetic

def pow_of_2(x): return ((x & (x - 1)) == 0)

Basically you need to check if exactly one bit is set to 1 in the binary representation. A more detailed explanation of how this works is here.

"Big O" of this power-of-2 function

1 Answers1