CODEWITHSUNDEEP
c++algorithmbit-manipulationbitwise-operators
Jagdish Parihar
Jagdish Parihar

Reputation: 34

Time complexity for finding if number is power of two

What is the time complexity of this code to find if the number is power of 2 or not.

Is it O(1)?

bool isPowerOfTwo(int x) {
    // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not
    return (x && !(x & (x - 1)));
}

LeetCode 231

Upvotes: 1

Views: 631

Answers (3)

Paul Hankin
Paul Hankin

Reputation: 58271

Informally it's O(1) because the code takes a bounded amount of time to run. It's not constant time as the runtime does depend on the input (for example, if x is 0, the function returns quickly), but it's bounded.

More formally, it's ambiguous because O(n) is defined for functions parameterized by arbitrarily large n, and here int is limited to 2^31 or 2^63. Often in complexity calculations of real programs this can be ignored (because an array of size 2^31 is very large), but here it's easy to think up numbers out of the range that your function accepts.

In practice, complexity theorists commonly generalize your problem in two ways

  • Either assume int contains Theta(log n) bits, and arithmetic operations work in O(1) time for Theta(log n) bits (that is, the size of memory cells and registers get larger as the input size increases). That's sometimes called the "word model".
  • Or assume that arithmetic operations are O(1) only for bit operations. That's sometimes called the "bit model".

In the word model, the function is O(1). In the bit model, the function is O(log n).

Note, if you replace int with a big-int type, then your function will certainly be O(log n).

Upvotes: 3

pradyumn Upadhyay
pradyumn Upadhyay

Reputation: 21

Yes, It is O(1), but Time complexity for bitwiseAnd(10^9,1) bitwiseAnd(10,1) are not same even though they both are O(1). In reality, there are 4 basic operations involved in your equation itself, which we consider as basic and unit operations in terms of the power of computing that it does. But in reality, These basic operations also have a cost of 32 or 64 operations as 32 or 64 bits are used to represent a number in most of the cases. So this O(1) time complexity means that the worst time complexity is of 32 or 64 operations in terms of computing and since 32 and 64 both are very low values and thses operations are performed on machine level so that's why we do not think much about the time these unit steps require to perform their function.

Upvotes: 1

tersrth
tersrth

Reputation: 889

Yes the code is time complexity O(1) because the running time is constant and does not depend on the size of the input.

Upvotes: 0

Related Questions