Re:I had to give a wrong answer to get the job (2017)
by remram on Friday July 23, 2021 @03:02PM
(#27934398)
To be clear, there is no tradeoff in the number of operations. You are doing the exact same number on average (or total or amortized), while improving the worst-case.
You do lose the ability to do a no-copy realloc() though, and increase the average memory use (not peak).
> As for the original interview question, there are systems where an occasional longer pause is not OK.
As you say, it's a tradeoff between worst-case operation cost and average operation cost: If you allow any worst-case operation cost, you can get really efficient on average. If you want really efficient worst-case operation cost, you can't get it down to exactly the average operation cost you could've otherwise gotten.
I wouldn't be surprised if this tradeoff is inherent to many de-amortization problems. But since the difference between the amortized and de-amortized solution is usually only a constant factor (as it is in this case), you have to be very specific about the model of computation if you want to prove anything mathematically.