What is the time complexity of the brute force iterative division approach to check if a number n is a power of four?

medium🪤 Complexity Trap Q13 of Q15

Bit Manipulation - Power of Four

AO(1) because division is constant time

BO(n) because it checks every number up to n

CO(log log n) because division by 4 reduces n faster than by 2

DO(log n) because the number is divided by 4 each iteration

Step-by-Step Solution

Solution:

Step 1: Analyze the loop iterations
Each iteration divides n by 4, so the number of iterations is proportional to log base 4 of n.
Step 2: Express complexity in Big-O notation
Since log base 4 of n is O(log n), the time complexity is O(log n).
Final Answer:
Option D -> Option D
Quick Check:
Loop runs ~log4(n) times, which is O(log n) [OK]

Quick Trick: Dividing by 4 reduces n logarithmically -> O(log n)

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Option D looks plausible since dividing by 4 is faster than 2, but log base change is constant factor, so complexity remains O(log n).

Interviewer Note:

CONTEXT

Tests understanding of logarithmic time complexity and common misconceptions about division steps.

Master "Power of Four" in Bit Manipulation

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

More Bit Manipulation Quizzes