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.