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.
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$.
