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

1 Answer 1

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$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .