Week 11 - Complexity of Heapsort Algorithm （episode3）

Firstly, I would like end this problem episodes. It is continued from last 2 weeks where I was at representing size of trees in regions of the Heap. The size of left subtree equals the sum of region 1's and region 3's which is 2^d - 1 where d represents the depth of heap.

Let n = 2^d + k, where 0 <= k < 2^d. The left subtree contains 2^(d-1) + j nodes and 0 <= j < 2^(d-1). If i = k - j. 0 <= i <= 2^(d-1), then n = 2^d + j + i and:

Size of left subtree / n = 2^(d-1) + j / 2^d + j + c <= 2^(d-1) + j / 2^d + j = f(j)

Let a = 2^(d-1). Then, f(j) = (a + j) / (2a + j)

f(0) = (a + 0) / (2a + 0) = 1/2

f(a) = 2a/3a = 2/3

f'(j) = a/(2a+j)^2 >= 0

So f is an increasing function that takes on a maximum at the left endpoint, and the max is 2/3. 

Then state result as a theorem:

If a heap A has size n, its subtrees have size less than or equal to 2n/3.

Applying this theorem to Equation of Heapify which is shown in episode 1, then

T*(n) = T(2n/3) + Θ(1).

Build Heap.

the complexity of BuildHeap appears to be  Θ(n lgn) - n calls tto Heapify at a cost of Θ(lgn) per call, but this result can be improved to Θ(n). 

Putting the results together with Equation of Heap sort in episode 1. Then the run-time complexity for HeapSort is,

T(n) = T*(n) + sum of T*(k) from 1 to (n-1) + Θ(n-1)

= Θ(n) + sum of lg k from 1 to (n-1) + Θ(n-1)

=  Θ(n lgn)