Trees
Any complete binary tree:
Layer / # of nodes in the layer / Size of each node in the layer / Total cost of the layer0 / 1 / ?
Unknown, can be any size / Cannot be calculated because we don’t know the size of nodes
1 / 2
2 / 22
..
i / 2i
…
h / 2h
In general, any node can be of any size, therefore the leaves do not have to be of size 1. So, in the general case, we cannot say that n/2h = 1 like we could for MergeSort. In the general case, we must calculate h from another known fact; for example, if we know that the total number of nodes is equal to n, i.e. by summing up the second column.
n = SUM[i=0, h] 2i
= (2h+1 -1)/(2-1)
=> h = Theta(lgn)
Any complete k-ary tree of:
Layer / # of nodes in the layer / Size of each node in the layer / Total cost of the layer0 / 1 / ?
Unknown, can be any size / Cannot be calculated because we don’t know the size of nodes
1 / k
2 / k2
..
i / ki
…
h / kh
The same argument as above: we don’t know the size of the nodes, so the height of the tree can be calculated if we know that the total number of nodes is n.
n = SUM[i=0, h] ki
= (kh+1 -1)/(k-1)
=> h = Theta(logkn) = Theta(lgn)
MergeSort() binary tree: T(n) = 2T(n/2) + n
0 / 1 / n / n
1 / 2 / n/2 / 2*n/2
2 / 22 / n/4 / 4*n/4
..
i / 2i / n/2i / 2i * n/2i
…
h / 2h / n/2h / n
Since leaves must be of size 1, then n/2h = 1 => h = log2n.
Total cost is obtained by summing the column 4:
T(n) = n+ n+ … + n = n*h = Theta(nlgn).
QuickSort binary tree: for the case that Partition() always splits into 1/3 and 2/3.
T(n) = T(n/3) + T(2n/3) + n tree is similar to the tree on page 151.
Layer / # of nodes in the layer / Size of each node in the layer,in the longest branch (the rightmost one) / Total cost of the layer
0 / 1 / n / n
1 / At most 2 / 2n/3 / at most n
2 / 22 * n/32 / at most n
..
i / At most 2i, because the left branches are shorter / 2i * n/3i / at most n
…
h / Definitely less than 2h / 2h * n/3h / At most n
Since leaf size must be equal to 1, (2/3)h * n = 1 => h = log3/2n.
The total cost is obtained by summing column 4, so T(n) = n* h = O(nlgn).
T(n) = 3T(n/4) + n2 tree, page 69.
0 / 1 / n2 / n2
1 / 3 / (n/4)2 / 3* (n/4)2
2 / 32 / (n/42)2 / 32 * (n/42)2
..
i / 3i / (n/4i)2 / 3i * (n/4i)2
…
h / 3h / (n/4h)2 / 3h * (n/4h)2
Since leaf size must be equal to 1, (n/4h)2= 1 => h = log4n.
The total cost is obtained by summing column 4:
T(n) = SUM[i=0, h] (3i * (n/4i)2)
= SUM[i=0, h] ((3i /42i ) * n2)
= n2 * SUM[i=0, h] (3i /42i ) // because n^2 doesn’t depend on i
= n2 * SUM[i=0, h] (3i /16i )
= n2 * SUM[i=0, h] (3/16)i
= n2 * ( ((3/16)h+1 -1) / (3/16 -1))
= n2 * ( ((3/16)* (3/16)h -1) / (-13/16)
= n2 * ( ((3/16)* (3/16)log4n -1) / (-13/16)
(3/16)log4n = nlog43/16 = nlog43/16 = nlog43 - log416 = nlog43 – 2 = nlog43 / n 2
T(n) = n2 * ( ((3/16)* nlog43 / n 2 -1) / (-13/16)
= ((3/16)* nlog43 - n2) / (-13/16)
= ((3/16)* n0.9 - n2) / (-13/16)
= Theta(n2)