Exponents in Big-O

Exponents show up in Big-O when algorithms branch or nest. $O(n^2)$ means two nested loops over $n$ items. $O(n^3)$ means three nested loops. These are polynomial and usually acceptable for small $n$.

$O(2^n)$ is exponential. It means the work doubles with every extra input element. At $n = 20$, that's about $10^6$ operations. At $n = 30$, about $10^9$. At $n = 40$, you're waiting hours.

The growth rate hierarchy you should remember: $O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$. Polynomial beats exponential for large $n$, which is why converting an $O(2^n)$ brute force into an $O(n^2)$ dynamic programming solution is such a big win.