Heapsort: Recursive Construction

Construct-Heap(n):

construct left subheap

construct right subheap

Restore-heap($1$)

Time Complexity:

$$W(n) = 2w(n/2)+ \log n$$ (8)

$$= \log n + 2w(n/2)$$ (9)

$$= \log n + 2 \left (\log (n/2) + 2w(\frac {n/2}2)\right)$$ (10)

$$= \log n + 2 \log n - 2\log 2 +$$ (11)

$$2^2w({n/2^2})$$ (12)

$$= \log n + 2 \log n - 2\log 2 +$$ (13)

$$2^2\left (\log(\frac n {2^2}) + 2w\left(\frac {n/2^2}2\right)\right)$$ (14)

$$= \log n + 2 \log n - 2\log 2 +$$ (15)

$$+ 2^2 \log n - 2^2\log (2^2) + 2^3w({n/2^3})$$ (16)

$$\cdots$$ (17)

$$= \log n + 2 \log n - 2\log 2 +$$ (18)

$$+ 2^2 \log n - 2^2\log (2^2) + \cdots +$$ (19)

$$2^k \log n - 2^k\log (2^k) + 2^{k+1}w({n/2^{k+1}})$$ (20)

$$= \log n(1+2+2^{2}+\cdots+2^{k})$$ (21)

$$-(2+2\cdot2^{2}+3\cdot2^{3}+\cdots +k\cdot2^{k})$$ (22)

Here, we assume that $n=2^k$ so $k = \log n.$


Let $s=2^{0}+2^{1}+2^{2}+\cdots+2^{k}$
$=\frac{2^{k+1}-1}{2-1}=2^{k+1}-1$


To derive this formula, one can follow these steps:

$$s =2^{0}+ 2^{1}+2^{2}+\cdots+2^{k}$$ (23)

$$2s = 2^{1}+2^{2}+\cdots+2^{k}+2^{k+1}$$ (24)

$$s = -1+2^{k+1}$$ (25)

Thus, $\sum_{i=0}^{k} 2^{i}=2^{k+1}-1$


Likewise, let

$$T =1\cdot 2^{1}+ 2\cdot 2^{2}+3\cdot2^{3}+\cdots+k\cdot2^{k}$$ (26)

$$2T = 1\cdot 2^{2}+2\cdot2^{3}+\cdots+$$ (27)

$$(k-1)\cdot2^{k}+ k2^{k+1}$$ (28)

$$T = -2^{1}-2^{2}-2^{3}-\cdots-2^{k}+$$ (29)

$$k2^{k+1}$$ (30)

$$= k2^{k+1}-(2^{1}+2^{2}+\cdots+2^{k})$$ (31)

$$= k2^{k+1}-(2^{k+1}-2)$$ (32)

$$= (k-1)2^{k+1}+2$$ (33)

$\Rightarrow W(n)= \log n(2^{K+1}-1)-((k-1)2^{k+1}+2)$
$=2n \log n- \log n-2n \log n+2n-2$
$=2n- \log n-2$
$=O(n)$