Time Complexity
Best: O(log n)
Avg: O(log n)
Worst: O(log n)
Binary Exponentiation computes aⁿ in O(log n) time by halving the exponent at each step instead of multiplying a by itself n times.
How it works:
1. Base case: a⁰ = 1
2. Recursively compute half = binPow(base, floor(exp / 2))
3. If exp is even, return half × half
4. If exp is odd, return half × half × base
Why it is fast:
Each recursive call cuts the exponent in half, so the recursion depth is proportional to log₂ n instead of n.
Time Complexity:
Best: O(log n)
Average: O(log n)
Worst: O(log n)
Space Complexity: O(log n) for the recursive call stack
Applications:
- Modular exponentiation in cryptography
- Fast matrix exponentiation
- Competitive programming and number theory
The key insight is that powers can be reused: once you know a^(n/2), you can square it to recover most of the work immediately.
Related algorithms
Frequently asked questions
- What is Binary Exponentiation?
- Binary Exponentiation computes aⁿ in O(log n) time by halving the exponent at each step instead of multiplying a by itself n times.
- What is the complexity of Binary Exponentiation?
- Time (average): O(log n) · Space: O(log n)
- Who is this Binary Exponentiation visualizer for?
- The Binary Exponentiation visualization targets intermediate-level learners in the Divide and Conquer category. Useful for students, interview prep, and hands-on review.
- What algorithms are related to Binary Exponentiation?
- In the same category (Divide and Conquer) you can explore: Tower of Hanoi. Each has an interactive visualization.