Terminology for worst-case N-complexity on $O(1)$ insert after amortisation

Question

Normally, when discussing amortisation and worst-case complexity, amortisation negates the worst-case scenarios, and the BigO describes the average for the operation (the way it's used in interviews nowadays).

For example, when an insertion of an element requires reallocation and copying of the array, increasing the size in two, it is still said that insertion is $O(1)$, not $O(n)$; the worst-case performance is rarely mentioned. Compare this with sorting algorithms, where the worst case could be $O(n^2)$, whereas the average case could be $O(n\log{}n)$, and this is always specified and discussed.

• What is the terminology to express this N-level complexity for the $O(1)$ insertion that requires reallocation with copy of $O(N)$ elements?

• What is the alternative terminology for expressing an optimisation approach, with delayed copy, where the worst-case complexity remains constant-time, provided the operation to allocate new chunk of memory itself is constant. In other words, where you keep both arrays, and do a lazy-copy approach.

Specifically, both of the above could be described as amortisation. But I'm having trouble finding out the absolutely correct terminology for this nuanced problem, as how do you distinguish between these two different scenarios in describing amortisation?!

Answer 1

Per Dmitri's hint on it being called de-amortisation, here's some applicable references on the subject:

• Rao Kosaraju S., Pop M. (1998) De-amortization of Algorithms. In: Hsu WL., Kao MY. (eds) Computing and Combinatorics. COCOON 1998. Lecture Notes in Computer Science, vol 1449. Springer, Berlin, Heidelberg

  Abstract: De-amortization aims to convert algorithms with excellent overall speed, $f(n)$ for performing n operations, into algorithms that take no more than $O(f(n)/n)$ steps for each operation. The paper reviews several existing techniques for de-amortization of algorithms.

  https://rd.springer.com/chapter/10.1007%2F3-540-68535-9_4

  https://doi.org/10.1007/3-540-68535-9_4

Answer 2

The case, when the operation performs the worst, is commonly called the worst case.

The common name for the optimization you mentioned is de-amortization.

To denote the fact that operations take $O(1)$ on average, you may say that the time complexity of a single operation is amortized $O(1)$.

As far as I know, amortized complexity analysis was first introduced by Robert Tarjan in his "Amortized Computational Complexity", where you can look up more usages of the term.

• cnst: Thank you! Any chance you can suggest how the whole thing should be discussed, e.g., if it is correct to ever say that the worst-case complexity of insertion is $O(n)$? If incorrect, what should be the complete and appropriate reply to such a statement on insertion complexity?
• Dmitri Urbanowicz: @cnst It is correct, but imprecise. It is more useful to call it amortized $O(1)$. Worst-case analysis may give an impression that some algorithms relying on this have quadratic time complexity, whereas they are linear.
• cnst: Thank you for the updates! So, "amortisation" was "discovered" as recently as 1983/1985, per the link you provide? I'm more interested in the topic of de-amortisation; long story short: someone on interviewing.io expected me to implement a queue with de-amortised $O(1)$ insertion, deletion and arbitrary peeking (any n-elements into the queue), all during a 40-minute phone interview, and I find that not only was their request totally unreasonable (they themselves admitted that the solution was "possible"), but that they didn't even use the correct terminology in discussing the whole thing.