# What is the amortized time complexity of inserting an element to this heap?

Assume you implement a heap using an array and each time the array is full, you copy it to an array double its size. What is the amortized time complexity (for the worst case) of inserting elements into the heap?

I think that we have $T(n) = n \cdot n$ (which is an upper bound on the total cost of a sequence of n operations in the worst case), and then the amortized complexity according to one formula is $\frac{T(n)}{n} = \frac{n^2}{n} = n$.

But I think it is very wrong because it is very clear from intuition that I should get $\log(n)$ ... So how should I calculate this?

• Ask yourself how often the worst case will happen. That's why we look at amortised time complexity. – gnasher729 Jun 13 '16 at 23:57