5

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

4
  • how did no one already have this username? Sep 2, 2014 at 22:07
  • 2
    @RyanHaining Usernames are not unique Sep 2, 2014 at 22:07
  • It's log2(n), not log2(10), and yes, it would be log5(n), but the constant would be bigger and algorithm more complicated.
    – soulcheck
    Sep 2, 2014 at 22:09
  • 1
    @StackOverflow in case of 5 subproblems imagine how difficult it is to actually merge them compared with 2 subproblems.
    – soulcheck
    Sep 2, 2014 at 22:13

1 Answer 1

4

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!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.