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?
If an operation, any operation, has an amortised cost of O(1), then performing it n times has cost O(n), by definition of “amortised cost”. Either your amortised cost is wrong, or your total cost is (assuming you change “O(n log n)” to “not O(n)”, to be a bit pedantic).