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!

(When logged in, completion status appears here.)

Previous Page Next Page