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?

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

Two very different operations are happening here, the doubling of the heap with its copy, and the insertion operations themselves. It sounds like you are fine on the insertion operations (where amortized analysis isn't needed), but for the doubling of the heap, you need a bit more help.

I don't want to post an answer to what might be a homework problem, but for that part of the problem, it looks very similar to how dynamic arrays work. If you consider the amortized analysis for dynamic arrays, and then just add the heap insertion operations to that, you will get something that works for insertion into heaps that can grow.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.