ALGORITHM

Question

H                                    HERE  MS = MERGE SORT , M = MERGE , WE ARE DOING ANALYSIS OF MERGE SORT HERE , CAN ANYONE TELL ME HOW THE  LEVEL IS         LOG N + 1  , THANKS  please help stuck in this

Answer 1

Suppose the input size is n
at level 0, we have a problem of size n
at level 1 , we have two sub problem of size n/2,

at level k , there are 2^k subproblem of size n/(2^k)

at leaf the size of each subproblem is 1 and total number of subproblem is n.

let leaf are at level k

n/(2^k) = 1

or, (2^k) = n

k = log(n)

at level log(n) ,  we get minimum sized sub problem.
so total number of level is log(n) + 1 (root at level 0).

Comments

bro  can u  explain me with  a diagram i got it but not perfectly please help

---

What do you want a abstract diagram  or a test case having n element?

---

can you tell me , see in image at lowest level we have , ms(1,1)  , ms(2,2) , ms(4,4) , ms(5,5)

and their size is 1 got it , but you said total no. of subproblem is  = n which in this case = 6

but at leaf we have only 4 , this is confusing me , if u can explain this then my problem will be solved :)

---

In my explanation, the merge sort divides the problem into exactly two halves at each level, so I get n subproblem at last level.