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.

  • $\begingroup$ Heapify is one example, and there are many more... geeksforgeeks.org/time-complexity-of-building-a-heap $\endgroup$
    – Avi Tal
    Commented 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$
    – newbie
    Commented Feb 27, 2021 at 2:34

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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