Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How come the height of recursion tree in merge sort lg(n)+1

Tags:

algorithm

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

like image 292
user3995169 Avatar asked Sep 29 '22 23:09

user3995169


1 Answers

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!

like image 134
Gene Avatar answered Oct 11 '22 15:10

Gene