0
$\begingroup$

I'm looking at the methods posted in https://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/ for checking whether n is a power of 2.

Method 5, pasted below, in the link claims to be O(1) but shouldn't it be O(log n)? When we do n & (n - 1), that's a bitwise operation over 32 bits (since n is a 32 bit integer), right?

bool isPowerOfTwo (int x)
{
    /* First x in the below expression is for the case when x is 0 */
    return x && (!(x&(x-1)));
}

Method 2, pasted below, claims to be O(log n), which I am not sure if it's correct either. The number of while loops is O(log n) and each while loop iteration is O(log n) (because we're bitwise-and'ing log n bits), so shouldn't it be O(log^2 n)?

bool isPowerOfTwo(int n)
{
    if (n == 0)
        return 0;
    while (n != 1)
    {
        if (n%2 != 0)
            return 0;
        n = n/2;
    }
    return 1;
}

I always get a bit confused with complexity analysis on the bit-scale.

$\endgroup$
7
  • $\begingroup$ Can you make your question self-contained? Also what cost model do you want to use? Also notice that if you fix an upper bound on the number of bits of $n$ (e.g., $32$), then any algorithm that terminates will necessarily take at most constant time (simply chose any constant not smaller than the maximum time needed when the algorithm is executed with inputs $0, 1, \dots, 2^{32}-1$). $\endgroup$
    – Steven
    Jul 19 at 20:39
  • $\begingroup$ @Steven Just made it self-contained. Let me check your cost model link and get back to you on that. I'm not well versed with complexity analysis -- I'm primarily just trying to learn enough to pass data structures and algorithms interviews (so nothing in depth). $\endgroup$
    – anonuser01
    Jul 19 at 20:43
  • $\begingroup$ @Steven By your logic of fixing the upper bound, then both algorithms in the OP would be O(1) space and time right? $\endgroup$
    – anonuser01
    Jul 19 at 20:44
  • $\begingroup$ Right. But you probably want to analyze the running time of the algorithm as a function of $n$, when $n$ grows. I..e, you are interested in the asymptotic running time of the algorithm. $\endgroup$
    – Steven
    Jul 19 at 20:44
  • $\begingroup$ @Steven Hmmm I'm not exactly sure which model is used. I think the uniform model may be what is used in interviews, but when it comes to bit manipulation questions, maybe the log model is used. So maybe we can analyze the complexity separately under each model? For method 2 in the OP, I think it's O(log n) under the uniform model and O(log^2 n) under the log model, and then method 5 seems to be O(1) and O(log n) under the uniform and log models, resp. $\endgroup$
    – anonuser01
    Jul 19 at 20:46
2
$\begingroup$

In the RAM model with uniform costs and word size $\Omega(\log n)$ the first algorithm requires $O(1)$ time since each word operation takes constant time.

The second algorithm requires time $O(\log n)$ since each iteration can be performed in $O(1)$ time and there are at most $O(\log n)$ iterations (after each iteration the value of $n$ is at most half the previous value).

If you want to use logarithmic cost model, then the first algorithm takes linear time in the number of bits of $n$, i.e., $O( \log n)$ time. The second algorithm (as written) takes $O(\log n)$ time per iteration to perform the comparison and to shift all the bits towards the right (this is the n=n/2 operation). The number of iterations is $O(\log n)$ as before. The overall running time is $O(\log^2 n)$.

All running times in this answer are tight (in the sense that if I said that an algorithm requires $O(f(n))$ time then there is a suitable infinite family of inputs that cause the algorithm to require $\Omega(f(n))$ time).

$\endgroup$
0
$\begingroup$

Well, in theory the first one is $O(\log n)$. In practice, if $n < 2^{64}$ for example, it is a fixed number of operations on a 64 bit processor. Likely to cost 1 or at most 2 nanoseconds. (And I would write it as (x & (x-1)) == 0 && x != 0, so the comparison x != 0 isn't done for all numbers, but only for numbers that are either powers of two or equal to 0). If n can be large, say 100s of bits, then for every 64 bit in n you have the same cost again.

And in theory, the second one is $O(\log^2 n)$, while in practice it is $O(\log n)$. Same reasoning.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.