Pattern Recognition Drill
Medium Recursion
The Problem
Compute x^n in O(log n) time.
What approach would you use?
Think about it before scrolling down.
If n even: (x^(n/2))². If n odd: x * x^(n-1). Halves n each step → O(log n) multiplications.
Common Trap
Naive loop of n multiplications is O(n). The 'square the half' insight is key to O(log n).