CODEWITHSUNDEEP
algorithmdata-structuresheaptime-complexityamortized-analysis
UFC Insider
UFC Insider

Reputation: 838

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

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 * 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 T(n) / n = n^n / n = n.

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

Upvotes: 1

Views: 1770

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

Imagine that you insert n elements into a heap represented this way. There are two different sources of costs you need to factor in:

  1. The cost of the heap operations, ignoring the underlying array resizes.
  2. The cost of the array resizes, ignoring the overarching heap operations.

The cost of (1) is O(n log n) across n total operations, since each heap insertion takes time O(log n).

For the cost of (2), notice that the work done to double the size of the array is directly proportional to the size of the array at the time that it's doubled. This means that you'll do 1 unit of work to double the array from size 1, 2 units of work to double the array from size 2, 4 units of work to double the array from size 4, etc. This means that the total work done is

1 + 2 + 4 + 8 + 16 + ... + 21 + log n ≤ 4n - 1 = O(n)

This math uses the fact that you only double the array at most 1 + log n times before it gets up to size n and that 1 + 2 + 4 + 8 + ... + 2k = 2k+1 - 1. This means that across all n insertions you do O(n) work doubling the array.

Overall, the total work done across n operations is O(n log n), so the amortized cost per operation is O(log n).

Upvotes: 2

Related Questions