Remember
- Big O describes how the count scales as n doubles: +1 for log n, x2 for n, x4 for n squared, squared for 2^n.
- O is an upper bound, Omega a lower bound, Theta both. All three only speak about n beyond some n0.
- Amortized cost is the total over a sequence divided by its length: rare expensive steps can still average O(1).