I read few questions with answers as suggested by stackoveflow. I am following Introduction to Algorithm by cormen book for my self study. Everything is been explained clearly in that book but the only thing that is not explained is how to calculate height of tree in merge sort analysis.
I am still on chapter 2 haven't gone far if that is explained in later chapters.
I want to ask if the top most node is divided 2 times and so on. It gives me a height of ln(n) which is log2(n) what if i divide the main problem in five subproblems. Would it have been log5(n) then? Please explain how is this expressed in logarithm as well why not in some linear term?
Thanks
Recursion trees represent self-calls in recursive procedures. Typical mergsort calls itself twice, each call sorting half the input, so the recursion tree is a complete binary tree.
Observe that complete binary trees of increasing height display a pattern in their numbers of nodes:
height new "layer" total nodes
(h) of nodes (N)
1 1 1
2 2 3
3 4 7
4 8 15
...
Each new layer at level L has 2^L nodes (where level 0 is the root). So it's easy to see that total nodes N as a function of h is just
N = 2^h - 1
Now solve for h:
h = log_2 (N + 1)
If you have a 5-way split and merge, then each node in the tree has 5 children, not two. The table becomes:
height new "layer" total nodes
(h) of nodes (N)
1 1 1
2 5 6
3 25 31
4 125 156
...
Here we have N = (5^h - 1) / 4. Solving for h,
h = log_5 (4N + 1)
In general for a K-way merge, the tree has N = (K^h - 1) / (K - 1), so the height is given by
h = log_K ((K - 1)N + 1) = O(log N) [the log's base doesn't matter to big-O]
However, be careful. In K-way mergesort, selecting each element to merge requires Theta(log K) time. You can't ignore this cost either theoretically or in practice!
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With