How can I prove that a build max heap's amortized cost is $O(n)$?

Question

Suppose a build max-heap operation runs bubble down over a heap. How does its amortized cost equal $O(n)$?

Answer 1

I assume that the operation build just turns an array into a heap by repairing the heap-property for every subtree bottom-up (let the operation for a single repair step called heapify).

It is not so hard to see, that heapify takes $O(h)$ steps, where $h$ is the height of the subtree to repair. We set $k=\lfloor \log n \rfloor $ as the height of heap. Notice that we have no more then $2^{(k-h)}$ subtrees of height $h$. So we can simply add up the costs as follows (we slightly abuse the big-O notation):

$$ \sum_{h=1}^k O(h) 2^{k-h} = 2^k \sum_{h=1}^k O(h)/2^{h}. $$

Since $\sum_{h=1}^\infty O(h)/2^{h}$ converges, we can upper bound the sum $\sum_{h=1}^k O(h)/2^{h}$ by a constant $C$. Thus we have that the running time for built is less than $C\cdot 2^k\le C \cdot n = O(n)$.

Answer 2

Note that here we don't have an arbitrary list of operations, we are talking about a single operation. So referring to it as amortized analysis can be confusing. Amortized analysis is usually used for an arbitrary list of operations, not a particular list of operations. We can use the methods for amortized analysis but AFAIK it is not common to call the result an amortized analysis.

Schulz answer is correct and uses the aggregate method. It is the usual proof of the fact and you can find it in textbooks like CLRS, chapter 6.

If you want to use the potential method for proving the bound, then remember that we want to get $O(1)$ for each heapify operation (to get $O(n)$ for the build heap operation). The real cost for each heapify is $O(h)$. We have to pay for the rest from the potential function. If we charge $c$ units for amortized cost then we can see that the analysis will work (we will determine $c$ later).

For the nodes in the bottom level (1) we will have to pay $n/2$. So we save potential $$cn/2-n/2$$

For the next level (2) we will pay $2n/4$ so we have potential $$c(n/2 + n/4) - (n/2 + 2n/4)$$

For the next level (3) we will pay $3n/8$ so we have potential $$c(n/2 + n/4 + n/8) - (n/2 + 2n/4 + 3n/8)$$

For the $k$th level we will pay $kn/2^i$ so we have potential $$cn\Sigma_{i=1}^k \frac{1}{2^i} - n\Sigma_{i=1}^k \frac{i}{2^i}$$

Note that $\Sigma_{i=1}^k \frac{i}{2^i} \leq d$ for some constant $d$ independent of $n$ and $k$ and $\Sigma_{i=1}^k \frac{1}{2^i} \geq \frac{1}{2}$. If we put these in the formula we get that the potential will always be at least $\frac{c}{2}n - dn$. So if we choose $c$ to be any constant larger than $2d$ it will always be positive.

The exact value of $c$ is not really important.

To cast this as an accounting method we need to specify which part of the data structure the potential is being assigned. In this case the potential needs to be assigned to the levels of the heap (if we want to assign the potential to nodes then it will be more complicated since it is difficult to tell which nodes will be use later when heapify is applied to nodes on higher levels).