<p>Heapify is one example:
<a href="https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/</a></p>
<p>Another simpler example (Min / Max queue):
<a href="https://www.geeksforgeeks.org/design-a-queue-data-structure-to-get-minimum-or-maximum-in-o1-time/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/design-a-queue-data-structure-to-get-minimum-or-maximum-in-o1-time/</a>  . This is also discussed here (see Szymon's answer): <a href="https://stackoverflow.com/questions/12054415/get-min-max-in-o1-time-from-a-queue">https://stackoverflow.com/questions/12054415/get-min-max-in-o1-time-from-a-queue</a></p>
<p>And there are many more...</p>

CC BY-SA 4.0
2021-02-27T11:01:23.723Z
2021-02-27T11:25:53.957Z
2021-02-27T11:25:53.957Z
Avi Tal
<p>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.</p>

CC BY-SA 4.0
2021-02-26T23:14:04.777Z
Heapify is one example, and there are many more...                https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/
Avi Tal
CC BY-SA 4.0
2021-02-27T02:34:14.507Z
@AviTal You're right, although this is definitely not what I've expected. Mind writing this as an answer?
newbie
<cc.complexity-theory><time-complexity>
Amortized time and worst case (non-amortized) separation
newbie
# Amortized time and worst case (non-amortized) separation

(Asked by: username_0 on 2021-02-26)

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.

**Tags:** cc.complexity-theory, time-complexity

> **Comments:**
> **username_1**: Heapify is one example, and there are many more...                https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/  
> **username_0**: @AviTal You're right, although this is definitely not what I've expected. Mind writing this as an answer?  

---

## 1 answers

### Answer by username_1 on 2021-02-27. Score: 0 | Accepted answer

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


---

