Algorithm with amortized time complexity

Question

While I understand the process of considering/observing an algorithm and finding an average time, necessary to perform an operation that happens in this algorithm, I still cannot quite gasp the idea, or rather the expression:

"The Algorithm has an amortized time complexity which is cost./linear etc".

What to understand when someone says the above expression?

One further question: Are the operations considered of the same type? What I mean by that, I'll try to showcase it with an example:

If we use pushback(), to input an element in an dynamic array, the operation here, is the input of an element. Sometimes the operation is cheap (in terms of the amount of times it requires to be executed) and sometimes is expensive. But there is only one type of operation here, the pushback operation. So can we talk about the amortized time of an algorithm, in other words can we talk about the average time for an operation, when different types of operations are taking place in the algorithm?

Sorry for the lack in my vocabulary. CS is not my major or main degree!

Answer 1

The amortized time is indeed the average time over a larger number of repetition of an operation (large enough that the variations are smoothed away).

A typical example is a growable array supporting push_back operations. When there is room at the end of the allocated space, a push_back costs $O(1)$. But when the allocated space is full, you increase it by doubling, and transfer all elements. This takes time $O(n)$, but only when $n$ is a power of $2$, so that the average remains $O(1)$.

In principle, only one operation is involved. In some cases, several can be (say insertions+deletions), provided this makes sense.

Answer 2

In my understanding, the statement "The Algorithm $A$ has an amortized time complexity which is linear" is something like $$\frac{1}{|\Sigma|^n} \sum_{w \in \Sigma^n} \text{running time of $A(w)$} = O(n)$$ i.e. the algorithm may behave badly on some examples, but the "average" case is good. It's something just as you thought when you talked about expectations.

For your second question, I think that for a certain algorithm, it can not know which operation it will perform when it runs on a particular input. It's some code like if (n >= 100) do(), something you can't know exactly how it behaves at runtime when you analyze the time complexity. So when you do the analysis, you can only say something like "the memory allocation will occur somewhere", rather than "the memory allocation will occur when $n\geq 100$, and the same for $n \geq 200$, $n \geq 300$": it's not a general case.

Answer 3

Take the other answers first...

What must not happen is for example an algorithm that always takes a long time if an array size goes from 100 to 101, 200 to 201 etc. if this also happens if I change the size from 100 to 101 to 100 to 101 to 100 to 101 and so on. In this situation the changes from 100 to 101 must not take long. Where "amortised execution time" works is if you increase the array size say be 50% if it is not enough, and shrink the array size if it is at 60% of the original size. So if 100->101 increases the array size, you'd have to remove 42 elements to get the size down to less than 60 to get a slow operation again and reduce the size to 100, and then you'd need another 42 operations to get back to 101 elements where you increase the size.

Another thing that doesn't count: If you want a sorted array all the time. Adding a random element to an array and keeping it sorted takes O(n). Starting with an empty array and adding n random items takes O(n^2) if the array needs to stay sorted all the time. If you only sort it at the very end, that's only O(n log n), but that is not amortised time.

Another thing to remember: In CS we are usually talking about time complexity. But assume that an operation can take either 10ns or 10µs on a real implementation. Both are O(1) but 10ns is what you would very much prefer in practice. Sometimes you find algorithms that are executed repeatedly that you can manipulate so that the expensive case happens only rarely.