# Proving recursion depth of merge sort

Hello I want to prove the recursion depth of merge sort, which is $$O(\log(n))$$. I think I can prove this by recurrence equation and the master theorem: $$T(N)=2 T(n/2)+O(N)$$ however i need to get $$O(\log(n))$$. Basically I want only to calculate the complexity of the deviding and remove the conquer part from this equation. How can I do this? Or is there another way to prove the height of the recursion tree?

In the picture below you can see I want to prove the height from red to gray.

• refer to recrusion tree method of solving recurrences. – Navjot Waraich May 15 at 11:07
• You can use the master theorem to prove the (worst-case) time complexity of mergesort. That does not give you a direct proof of the height of the comparison tree. – dkaeae May 15 at 11:23
• solved with recrusion tree method thanks @NavjotWaraich – raviolican May 15 at 12:00
• @raviolican Consider answering your own question. It might be helpful for future readers. – dkaeae May 15 at 12:12

## 1 Answer

First of all, let me correct the recursion for the running time of merge sort: $$T(n) = \begin{cases} T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + \Theta(n) & \text{if } n > 1, \\ \Theta(1) & \text{if } n = 1. \end{cases}$$ The corresponding recursion for depth is: $$D(n) = \begin{cases} \max(D(\lfloor n/2 \rfloor), D(\lceil n/2 \rceil)) + 1 & \text{if } n > 1, \\ 0 & \text{if } n = 1. \end{cases}$$ (The value of $$D(1)$$ could also be $$1$$, depending on how you define depth.)

The solution of this recurrence is $$D(n) =\lceil \log_2 n \rceil$$.

When $$n$$ is a power of 2, you can calculate the depth of the recursion tree by noticing that the value of $$n$$ decreases by a factor of 2 at each level. For the general case, the main observation is that the depth is monotone in $$n$$, using which you can easily conclude $$D(n) \leq \lceil \log_2 n \rceil$$ by considering the smallest power of 2 which is at least $$n$$.