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 worse 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 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

    So I suppose I shouldn't worry that if I were ever lucky enough to buy a jackpot-winning lottery ticket, I'd also be unlucky and have it destroyed by a bolt of lightning.

  • LHS Cow speaking

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

  • Goat speaking

    Meh, and the worst case isn't very helpful for expected-time algorithms.

  • LHS Cow speaking

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

(When logged in, completion status appears here.)