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*}
$\endgroup$
2
  • $\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$ Commented May 15, 2014 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
    Commented May 15, 2014 at 6:23

1 Answer 1

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.

$\endgroup$

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