Assume a reasonable computation model (thinking about pointer machine or RAM model), is there a problem where there is a clear separation between amortized and worst case complexity? Say, if amortization is not allowed and only worst case for each operation is considered, the time complexity will be (provably) higher. Notice that this is different from random self-reducibility.
2
-
$\begingroup$ Heapify is one example, and there are many more... geeksforgeeks.org/time-complexity-of-building-a-heap $\endgroup$– Avi TalCommented Feb 26, 2021 at 23:14
-
$\begingroup$ @AviTal You're right, although this is definitely not what I've expected. Mind writing this as an answer? $\endgroup$– newbieCommented Feb 27, 2021 at 2:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Heapify is one example: https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/
Another simpler example (Min / Max queue): https://www.geeksforgeeks.org/design-a-queue-data-structure-to-get-minimum-or-maximum-in-o1-time/ . This is also discussed here (see Szymon's answer): https://stackoverflow.com/questions/12054415/get-min-max-in-o1-time-from-a-queue
And there are many more...
