# Amortized analysis of max-heap

Consider an ordinary binary max-heap data structure with $$n$$ elements that supports insert and extract-max in $$O(\log n)$$ worst-case time.

Question: If extract max is $$O(1)$$ amortized does that mean worst case is $$O(n)$$?

My answer: No, A sequence of $$n$$ EXTRACT_MAX will cost $$O(n\log n)$$. This is because in a Heap the leaves are almost on the same level and the number of leaves in a Heap is $$O(n/2) = O(n)$$. Calling EXTRACT_MAX each time removes the maximum element from the root and replace it with a new second maximum element and decrement a leaf. Thus, decrementing all the leaves (which are of $$O(n)$$) will take $$O(\log n)$$ time each as all leaves are almost in the same level totally giving a time complexity of $$O(n\log n)^{1/4}$$.

Does this make sense?

• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. – D.W. Mar 13 '19 at 23:47

Your proposed answer contradicts itself, so no, it doesn't make sense. It starts by saying it will take $$O(n \log n)$$ time and concludes by saying it will take time $$O(n \log n)^{1/4}$$ time. You need to decide which you mean. And it's not clear where the $$1/4$$ came from.