Given the potential function $\phi$, it seems that remove max may take $O(1)$ amoratized, meaning that $n$ removals would take $O(n)$, which can't be, as it means we get a linear time comparison based sort if we build the heap in $O(n)$.

Where is the falling point in this potential function, and does it not give a $O(1)$ time guarantee and why?

\begin{align*} \overline C_i =& C_i + \phi_i-\phi_{i-1} \\ \phi_i =& \sum_{a\in Heap}{depth(a)} \\ \end{align*}

  • meaning the potential function is the sum of depths of all nodes in the tree. \begin{align*} C_i &= \log n \\ \phi_{i} &= \phi_{i-1} - \log n \\ \overline C_i &= \log n + \phi_{i-1} - \log n - \phi_{i-1} = 0 \end{align*}

closed as unclear what you're asking by D.W., Luke Mathieson, vonbrand, David Richerby, Joe May 15 '14 at 4:54

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ This is a dump of a problem, not a question. If you have a specific question regarding the wording of the problem or about concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – David Richerby May 15 '14 at 2:04
  • $\begingroup$ @DavidRicherby This is not a dump of a question. This is a problem I encountered and I worded the problem I had, including the steps I took, and I'm asking where I'm wrong. $\endgroup$ – NightRa May 15 '14 at 6:23

Amortized analysis relies on $\sum_{i=1}^n \overline{C_i} = \sum_{i=1}^n C_i+\phi_n-\phi_0$ being an upper bound for $\sum_{i=1}^n C_i$. This requires $\phi_n$ to be at least as large as $\phi_0$. Your potential function does not satisfy this requirement, aince $\phi$ will get smaller with each step.


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