Math for coding interviews/Exponents - doubling chains
Why 2^n Exponential Time Is Too Slow
2ⁿ means you start with 1 and double it n times. n=10 gives you 1,024. n=20 gives you 1,048,576. n=30 gives you over a billion. It grows terrifyingly fast.
See it for yourself
A curve that looks almost flat near zero, then bends upward so steeply it nearly goes straight up. Compare it side by side with a straight line (linear) and the difference is shocking.
Exponents - doubling chains
2ⁿ means you start with 1 and double it n times. n=10 gives you 1,024. n=20 gives you 1,048,576. n=30 gives you over a billion. It grows terrifyingly fast.
Think of it this way: A chain letter. You send it to 2 friends. Each of them sends it to 2 friends. After 30 rounds, over a billion letters have been sent.
For algorithms: Brute-force recursive solutions that branch into 2 sub-problems at every step hit O(2ⁿ). That is why memoization and dynamic programming matter so much.
Real-world analogy
A chain letter. You send it to 2 friends. Each of them sends it to 2 friends. After 30 rounds, over a billion letters have been sent.
Why it matters in interviews
Brute-force recursive solutions that branch into 2 sub-problems at every step hit O(2ⁿ). That is why memoization and dynamic programming matter so much.