I have read that average case analysis makes some assumptions about the inputs to the data structure, and amortized analysis makes no such assumptions.

Does amortized analysis make any assumptions about the sequence of function calls to the data structure though?

I had had a dynamically sized stack (via an array) which only expanded the capacity by 1 element when it needed to expand the size, could I say that the amortized cost of this structure is $O(n)$ since I cannot guarantee that $pop()$ will ever be called?

Or should it still take $pop()$ into account therefore making an assumption about the sequence of function calls?

  • $\begingroup$ No assumptions. $\endgroup$ May 8, 2020 at 5:26
  • $\begingroup$ @YuvalFilmus thanks, in that case is my analysis of the stack correct? $\endgroup$
    – Joff
    May 8, 2020 at 5:35
  • $\begingroup$ You haven’t provided a complete analysis. To show that the amortized running time is large, all you need to do is give a bad sequence of operations. $\endgroup$ May 8, 2020 at 5:37
  • $\begingroup$ right, which would cause a copy of every element and resize for every push and thus $O(n)$. Is that complete? $\endgroup$
    – Joff
    May 8, 2020 at 5:47
  • $\begingroup$ Recall that $O(n)$ is only an upper bound. You sequence of operations also takes $O(n!)$ time, but so what. You need a lower bound ($\Omega$) or a tight bound ($\Theta$). You also need to describe a complete sequence of $m$ operations with takes $Tm$ time, which will imply that the amortized running time is at least $T$. $\endgroup$ May 8, 2020 at 5:56


Your Answer

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

Browse other questions tagged or ask your own question.