Pattern visualizer
Power of a Number (Fast Exponentiation)
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. Animated on: Compute x^n where x = 3, n = 5, using fast (binary) exponentiation..
Halve the exponent, square the result
time O(log n)space O(log n) call stackstep 1 / 9
5
[0]4
[1]2
[2]1
[3]0
[4]line 4
power(3,5): n=5 is odd, so recurse into power(3,4) — we'll multiply by x once that result comes back.
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