CS 70

Key Points

  • Expected-Time Reminder:

    • Expected time describes the performance of an algorithm with some amount of randomness. Time for individual operations will come from a probability distribution. In practice, probabilities may be a sufficient guarantee, but from a theoretical perspective worst-case behavior is possible even if it is unlikely.

  • An amortized bound promises that the total complexity of a sequence of operations is bounded by the sum of the amortized times of the individual operations.

    • Only applies to the total complexity of the sequence of operations from the very beginning.
    • It does not give a bound for a the time complexity of a single operation, time for individual operations can vary significantly.
    • A useful fiction: even though some operations are expensive and some are cheap, an amortized bound spreads the cost evenly.
    • Everyday analogy: it's like a professor keeping you an extra ten minutes past when class should have ended because the previous two classes ended five minutes early

  • Aggregate method:

    • Consider an arbitrary sequence of operations.
    • Analyze its complexity.
    • Divide by the number of operations to get an amortized bound.

  • Array-backed list analysis:

    • With capacity doubling, amortized \( \Theta(1) \) push_back.
    • With capacity halving, amortized \( \Theta(1) \) pop_back.

  • Splay Trees:

    • Self-balancing tree with amortized \( \mathrm{O}( \log{n} ) \) insert/lookup, \( \mathrm{O}(n) \) worst-case.
    • Really efficient when lookups have high locality (lookups tend to repeat).
    • Every inserted/looked-up node is rotated to the root.
      • Recently inserted/found nodes are easy to find (near best-case time).
      • No space overhead!
    • Inspiration for this song by Dani Demas, HMC '15! (Warning: banjo.)

Bonus Material: The Banker's Method

If you'd like to dive deeper into amortized time (or would just like another perspective on it), these two (optional!) videos explain the concept from the perspective of the banker's method.

(When logged in, completion status appears here.)