Check if Number is Power of Two in DSA C - Time & Space Complexity

Time Complexity: Check if Number is Power of Two

O(1)

Understanding Time Complexity

We want to know how fast we can check if a number is a power of two.

The question is: how does the time needed change as the number gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdbool.h>

bool isPowerOfTwo(unsigned int n) {
    return (n & (n - 1)) == 0 && n != 0;
}
    

This code checks if a number is a power of two using a bitwise trick.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single bitwise AND operation and a subtraction.
• How many times: Exactly once, no loops or recursion.

How Execution Grows With Input

Since the code does only one check regardless of input size, the time stays the same.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The number of operations does not grow with input size; it stays constant.

Final Time Complexity

Time Complexity: O(1)

This means the check takes the same amount of time no matter how big the number is.

Common Mistake

[X] Wrong: "We need to divide or loop through the number to check if it is a power of two."

[OK] Correct: This bitwise method does the check instantly without loops or division, so it is much faster.

Interview Connect

Knowing this quick check shows you understand bitwise operations and efficiency, a skill valued in many coding challenges.

Self-Check

"What if we changed the input type to a signed integer? How would the time complexity change?"