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?
What is the amortized time complexity of inserting an element to this heap?
algorithm analysis;data structures;runtime analysis;heaps;amortized analysis