2
$\begingroup$

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*}
| cite | improve this question | | | | |
$\endgroup$
  • $\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
3
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$

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