# Algorithm with amortized time complexity

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!

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.

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.