Pow(x, n) (Fast Exponentiation)
Halve the exponent, square the result
time O(log n)space O(log n) call stack
Multiplying x by itself n times is O(n). Fast exponentiation does better by noticing x^n = (x^(n/2))^2 when n is even — so halving n each time only takes O(log n) recursive calls. When n is odd, peel off one factor of x first (x^n = x * x^(n-1)) to make the exponent even again, then apply the same halving trick.
Details
Animated on: Compute x^n where x = 3, n = 5, using fast (binary) exponentiation.
Problem:Pow(x, n) (Fast Exponentiation)Medium
Halve the exponent, square the result
step 1 / 9
5
[0]4
[1]2
[2]1
[3]0
[4]power(3,5): n=5 is odd, so recurse into power(3,4) — we'll multiply by x once that result comes back.
- call=0· arr[0] = 5
Pseudocode
1FUNCTION power(x, n):2 IF n == 0: RETURN 13 IF n is odd:4 RETURN x * power(x, n - 1)5 half = power(x, n / 2)6 RETURN half * half
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- power(3,5): n=5 is odd, so recurse into power(3,4) — we'll multiply by x once that result comes back.
- power(3,4): n=4 is even, so recurse into power(3,2) — the result will be squared (half*half).
- power(3,2): n=2 is even, recurse into power(3,1), then square the result.
- power(3,1): n=1 is odd, recurse into power(3,0).
- power(3,0): base case — n is 0, return 1. This is the deepest call; now we unwind.
- Unwind: power(3,1) = 3 * power(3,0) = 3 * 1 = 3 (odd case multiplies by x once).
- power(3,2) = half * half = 3 * 3 = 9 (even case squares the half-power).
- power(3,4) = half * half = 9 * 9 = 81.
- power(3,5) = 3 * power(3,4) = 3 * 81 = 243. Final answer: 243.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.