1
$\begingroup$

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.

$\endgroup$
2
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.