2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So if I provide 2\$ for each node that I build. So if we have n nodes , we have to make sure our bank doesn't run out of 2n\$. DOn't know how to proof it using induction. $\endgroup$ – user1675999 Nov 14 '12 at 5:27
  • $\begingroup$ Give a little more information how the build operation works. $\endgroup$ – A.Schulz Nov 14 '12 at 7:01
  • 1
    $\begingroup$ Note that the $O(n)$ cost to build a heap is in the worst-case, it is not amortized. $\endgroup$ – Massimo Cafaro Nov 16 '12 at 9:30
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hey guys, thanks for the reply. I actually came up with this, but I was struggling to prove the ammortised cost analysis, that at any node x of a tree, whose height is h, such that i put 2$ on each node. Then when i run max_heapify from that node, i will have h+1$ left in my credit. $\endgroup$ – user1675999 Nov 21 '12 at 6:14
  • $\begingroup$ Are you asking why heapify takes $O(h)$? There a definitely different ways how to do the analysis. You should notice that we are not talking about amortized costs, since we only consider one single build operation. Of course you can amortize the costs of the heapify operations, but you can also just sum them up, that is what I did. $\endgroup$ – A.Schulz Nov 21 '12 at 7:23
2
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

Algorithm of Build Heap:

BUILD-HEAP(A) heapsize := size(A); for i := floor(heapsize/2) down to 1 do HEAPIFY(A, i); end for END

A quick look over the above algorithm suggests that the running time is O(nlogn), since each call to Heapify costs O(logn) and Build-Heap makes O(n) such calls. This upper bound, though correct, is not asymptotically tight.

As we know that heapify is called for all internal nodes, and heapify takes O(logn) time, but this is not exactly the case. In reality, the O(logn) time is taken by root only, as root is at the height logn, time varies for the internal nodes with different height. For example, for the internal nodes at the second last level, heapify will take O(h) time for all the nodes at that level where h=1, for the internal nodes at the third last level, heapify will take O(h) time for all the nodes at that level where h=2, therefore depending height time to heapify is changing. So considering this, we can derive a tighter upper bound than O(nLogn).

For finding the Time Complexity of building a heap, we must know the number of nodes having height h. For this we use the fact that, A heap of size n has at most ceil( n / 2^(h+1) ) Now to derive the time complexity, we express the total cost of Build-Heap as-

T(n)= ceil( n / 2^(h+1 )) * O(h) = n/2 * h / (2^h) =O( n * h /( 2^h) )

Step 3 uses the properties of the Big-Oh notation to ignore the ceiling function and the constant 2 ( since 2^(h+1) = 2.(2^h) = O(2^h) ), and the upper limit of the summation can be increased to infinity since we are using Big-Oh notation. Here we will consider that ‘h’( means the height) tends to infinity for the worst case time complexity.

Now, ∑ h / 2^h = (0 / 2^0) + (1 / 2^1) + (2 / 2^2) + (3 / 2^3) + (4 / 2^4) + ……….

= 0/1 + 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + …………. ------------> eqn 1

Now, if we divide the whole equation from 2 we get,

∑ h / 2.(2^h) = 0 / 2.(2^0) + 1 / 2.(2^1) +2 / 2.(2^2) +3 / 2.(2^3) +4 / 2.(2^4) + …….

= 0/2 + 1/4 + 2/8 + 3/16 + 4/32 + 5/64 + ………….. ------------> eqn 2

Now, subtracting (eqn 1 – eqn 2) —->we get,

∑ h / (2^h) - h /( 2.(2^h)) = 1/2+ 1/4 + 1/16 + 1/32 + ……………. + 1/∞

=> ∑ 1/2(h / 2^h) = 1/2 / (1 – 1/2) (using formula for infinite GP, sum = a / (1-r))

=> ∑ h / 2^h = 2

Therefore, T(n) = O( n * h /( 2^h) ) = O(n * 2) = O(n),

So, time complexity of build-heap is O(n).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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