2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Mar 13, 2019 at 23:47

2 Answers 2

Reset to default
1
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ so that means it can be processed in O(n) times ? $\endgroup$
    – bobsag bob
    Mar 13, 2019 at 21:56
  • $\begingroup$ No. It means the O(1) claim for amortised cost is wrong, or it can be processed in O(n). $\endgroup$
    – gnasher729
    Mar 13, 2019 at 22:48
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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