Check if Number is Power of Two in DSA Python - 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.

How does the time to check grow as the number gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def is_power_of_two(n: int) -> bool:
    if n <= 0:
        return False
    return (n & (n - 1)) == 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 subtraction.
• How many times: Exactly once, no loops or recursion.

How Execution Grows With Input

The number of steps stays the same no matter how big the number is.

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

Pattern observation: The work does not increase as the number grows.

Final Time Complexity

Time Complexity: O(1)

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

Common Mistake

[X] Wrong: "Checking if a number is a power of two requires looping through all smaller numbers."

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

Interview Connect

Knowing this quick check shows you understand efficient bitwise operations, a useful skill in many coding problems.

Self-Check

"What if we changed the input to allow zero and negative numbers? How would the time complexity change?"