Bit Manipulation - Power of Four
What is the worst-case time complexity of repeatedly dividing a positive integer n by 4 until it becomes 1 or not divisible by 4?
What is the worst-case time complexity of repeatedly dividing a positive integer n by 4 until it becomes 1 or not divisible by 4?
medium💡 Conceptual Thinking Q5 of Q15
Step-by-Step Solution
Solution:
Step 1: Understand the division process
Each division reduces n by a factor of 4.Step 2: Calculate number of divisions
The number of divisions until n becomes 1 is the exponent k such that n = 4^k, which is log base 4 of n.Final Answer:
Option D -> Option DQuick Check:
Repeated division by 4 reduces n exponentially [OK]
Quick Trick: Repeated division by 4 takes O(log base 4 n) steps [OK]
Common Mistakes:
MISTAKES- Confusing log base 4 with log base 2
- Assuming constant time due to division
- Mistaking linear time complexity
Trap Explanation:
PITFALL- Option D looks plausible because log base 2 is common, but division by 4 means log base 4.
Interviewer Note:
CONTEXT- Tests understanding of logarithmic time complexity in iterative division.
Master "Power of Four" in Bit Manipulation
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Bit Manipulation Quizzes