Tighter Bound on heapify

I want to calculate the tighter bound on heapify using siftdown approach so I proceeded as follows :

At each level i, each key on that level can go to leaf level h (where h is height of tree) in the worst case.

As there are 2ⁱ nodes at level i, so total work done is

∑_0≤i≤h (h - i ) * 2ⁱ

But I couldn't proceed further. I know it开发者_开发问答 has to come O(n) but I couldn't reach it. Please help me solving this.

S = ∑_0≤i≤h (h - i ) * 2ⁱ

S = h + 2(h - 1) + 4(h - 2) + ... + 2^{h - 1} ... (1)

Multiply both sides by 2,

2S = 2h + 4(h - 1) + 8(h - 2) + ... + 2^h ... (2)

Subtract from (1) from (2),

S = h -2h + 2 + 4 + 8 + …. + 2^h

= -h – 1 + (1 + 2 + 4 + 8 +… + 2^h )

= (2^{h + 1} - 1) – (h + 1)

[Note: 1 + 2 + 4 + 8 + ... + 2^h = (2^{h + 1} - 1)

Since a complete binary tree of height h has between 2h and 2h + 1 nodes, the above sum is O(n) where n is the number of nodes in the heap.

It's a little easier to see if instead of your i running from the top, you count from the bottom. So if we say i is the height from the bottom we transform your sum into:

∑ i * 2^h-i

= 2^h * ∑ i / 2ⁱ

= 2^h * O(1)

= O(2^logn) = O(n)

I swapped h with logn since this is a binary heap.

I'll justify why that sum is O(1):

The sum is a finite sum of the terms i/2ⁱ, so if we show convergence of the infinite sum (i-->infinite) then obviously every finite sum (i.e. for all n) will sum to less than that value (since all terms are positive). Meaning every finite sum is bounded by a constant, i.e. O(1).

We are left with just the proof that the infinite ∑ i / 2ⁱ converges. We can use a myriad of convergence tests, let's use the simple result that ∑ 1 / i² converges and show that for large enough i that will upper bound our sum:

We want to show that for large enough i:

i/2ⁱ < 1/i²

which happens iff i³ < 2ⁱ which is true for, say, i > 10

QED