CS 70

Before You Start…

Suppose that on a particular machine, we have a choice between three different options for a C++ stack implementation:

  • Stack W: 4 microseconds worst-case time per push
  • Stack E: 3 microseconds expected time per push
    • Times are normally distributed, with a standard deviation of 1 microsecond.
  • Stack A: 2 microseconds amortized time per push

Which option might take the longest on the very first push onto the stack?

And why?

At this point, Stack W will take (at most) 4 microseconds, and Stack A will take at most 2 microseconds. Both could be faster, but we're concerned about which might take the longest so that's incidental here.

In contrast, Stack E is expected to take 3 microseconds, but there is a 15.8% chance that it'll take more than 4 microseconds. So Stack E is the worst option.

Suppose we've previously pushed 300 million items onto the stack, and now we're about to push one more. Which option could take the longest time for this push, and why?

Stack W will take (at most) 4 microseconds, as always.

Stack A, however, could have been “saving up” time to use later. Thus, in the worst case all the amortized time it charged us could have been saved, and now it's decided to use it. In that case, the time used so far is zero, and the time for this step is 600 million microseconds, or 10 minutes. Even if it only actually banked one of those microseconds each time to use later, we could still be waiting five minutes.

  • Goat speaking

    They shouldn't call it amortization, they should call it procrastination!

  • Duck speaking

    Definitely seems like the worst.

In theory, though, Stack E could be worse. It's a normal distribution, so although the expected value is 3 microseconds, there is a \( 1 \) in \( 2.54 \times 10^{77,396} \) chance it will take more than ten minutes.

  • Goat speaking

    That's ridiculous! You didn't really expect us to give that answer, did you?

  • LHS Cow speaking

    We'd accept either answer, but…

From a practical standpoint, the probability is vanishingly small. When it's that unlikely, it makes no sense to seriously consider the possibility that it could happen.

  • Hedgehog speaking

    Sometimes I worry that if I were ever lucky enough to buy a jackpot-winning lottery ticket, it would happen on a day when unlikely things were happening, and just as I was celebrating my win, I'd be struck by lightning.

  • LHS Cow speaking

    Yes, it could, happen that way, but it's really not something to lose any sleep thinking about. Although we can work out the chance of hitting the jackpot and then being struck by lightning mathematically, in practice that chance is so vanishingly small that we can confidently say it will never actually happen to anyone.

  • Goat speaking

    Meh. The worst case isn't very helpful for expected-time algorithms.

  • LHS Cow speaking

    You definitely need to think about how likely that worst case is.

(When logged in, completion status appears here.)