Why merge recursion tree height sorts lg (n) +1

Question

I read a few questions with answers suggested by stackoveflow. I follow the introduction to the cormen book algorithm for my study. This book explains everything clearly, but the only thing that is not explained is how to calculate the height of a tree in a merge sort analysis.

I still did not go far in chapter two if this is explained in subsequent chapters.

I want to ask if the top maximum node is divided 2 times, etc. This gives me the height ln (n), which is log ₂ (n), if I divide the main problem into five subtasks. Will it be log ₅ (n) then? Please explain how this is expressed in a logarithm, and why not in some linear way?

thank

Answer 1

Recursion trees represent independent calls in recursive procedures. A typical mergsort calls itself twice, each call sorts half of the input, so the recursion tree is a complete binary tree.

Please note that full binary trees with increasing height display a template in their number 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 level at level L has 2 ^ L-nodes (where level 0 is the root). Thus, it is easy to see that the total nodes of N as a function of h are simply

N = 2^h - 1

Now solve for h:

h = log_2 (N + 1)

If you have 5-way splitting and merging, 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. Solution for h,

h = log_5 (4N + 1)

K- N = (K ^ h - 1)/(K - 1),

h = log_K ((K - 1)N + 1) = O(log N)    [the log base doesn't matter to big-O]

. K-way mergesort Theta (log K). , !