Characterizing Operation Cost that Varies

The problem is that \(\mathrm{O}(n)\) is very vague. It's saying that performance could be as bad as \(\Theta(n)\) but it might not be. In the case of our in-order BST iterator, \(\Theta(n)\) was the worst case, but that worst case could not occur often.

Worst Case Is Often Too Pessimistic

When the worst case doesn't happen often, it can be a misleading metric. Let's look at another example to explore this situation.

The Red Card–Blue Card Pairing Game

Suppose we have two decks of \(n\) playing cards (e.g., \(n = 52\)). One is red, the other is blue.

You keep red cards. Whenever you get a blue card, you must take a red card from your hand, and put the pair (red and blue) on the table in front of you.

At each turn of the game, the dealer gives you

• One new red card; and,
• Zero or more blue cards.
  • You don't know how many blue cards you'll get on a given turn; but,
  • The dealer can't give you more blue cards than the number of unpaired red cards (i.e., the number you hold in your hand).

The game stops when the dealer runs out of red cards to give you.

[Precisionist details: You need to pair each blue card with a unique red card when you receive it—you can't leave blue cards unpaired or reuse the same card for multiple pairings. Cards are never put back in the deck during the game. Other details of the game need not concern us; feel free to make up a pairing game with these rules as a foundation.]

Examples

The dealer could give you a red card and a blue card every turn until all the cards are gone, or they could give you no blue cards at all until the very last red card, at which point they give you the entire deck of blue cards. The animated GIFs below show these two scenarios.

Here are some other ways that cards might be dealt:

Worst-Case Blue Cards

Based on the “all cards on the last turn” example, the worst-case number of blue cards you could be given on any turn is \( \Theta(n) \).

Let's suppose we have a 52-card deck. Saying \(\Theta(n)\) as the worst case for each turn might give the impression that we could receive 2704 blue cards (\( 52^2 \)) total. It's true that we could be given all 52 in one turn, or half-deck sized chunks in two turns, but overall, across all turns, we'll still only be given at most 52 cards.

And so we introduce a new concept: amortized time.

Amortized Time

Here's the definition of amortized time:

Example: In our card game, we can say that we receive one amortized blue card per turn. At the end, after 52 turns, we will have at most 52 blue cards.

Note that amortized time is a kind of “average” time. When we say our card game has one amortized blue card per turn, it doesn't mean that we'll only get one blue card, it means that on average we get one blue card per turn, an average with some very specific guarantees about the maximum number of blue cards that can have been handed out in total.

After \( m \) turns, you have \( m \) red cards because you get one red card per turn. Each red card is either

• Paired up with a blue card, or
• Unpaired (and you are never allowed to be given more blue cards than the number of unpaired red cards).

Thus, you have at most \( m \) blue cards, with every red card paired.

One way of thinking about the problem is to say that for each step you receive a red card, you are either dealt a blue card to go with it, or there's an undealt blue card that's been set aside to give you later (and will be that red card's eventual pairing partner). If you had to pay $1 every time you got dealt a blue card, one way to ensure you'll always have the right amount of money would be to set aside $1 each time you get a red card—the corresponding blue card to pair with it will be coming along a some point, and you might as well put the $1 aside for it now so you're ready if you suddenly get a bunch of blue cards at once. (FWIW, this financial analogy is where the term amortization comes from.)

(When logged in, completion status appears here.)

Previous Page Next Page