Merge Sort time complexity analysis

Question

How can I prove that $T(n) = 2T(n/2) + n$ is $O(n \log n)$ ?

Answer 1

There are two ideas to do this. The first one is telescoping where you recursively use the definition of $T(n)$ or you could of course use induction (this almost always works). For a sketch of the proof check page 3 here. Note that here it is assumed that $n$ is a power of 2 making the proof simpler, if not it goes in the same fashion nevertheless.

Answer 2

HINT:

Use induction to show that there are constants $c$ and $n_0$ s.t. $T(n) \leq c \cdot n \log n \quad\forall n \geq n_0$. Use $T(2)$ as your base case. Remember cool log properties to reduce the logarithm and to use the induction hypothesis.

Post your progress if you get stuck.

Answer 3

Let $L(k)=T(2^k)$ and $n = 2^k$. Then $L(k)=T(n)$, $L(k-1)=T(n/2)$, and thus, $$ L(k)=2L(k-1)+2^k\tag1 $$ Multiplying $(1)$ by $2^{-k}$ gives $$ \overbrace{2^{-k}L(k)}^{a_k}=\overbrace{2^{-(k-1)}L(k-1)}^{a_{k-1}}+1\tag2 $$ Iterating $(2)$, we get $$ 2^{-k}L(k)=L(0)+k\tag3 $$ which means $$ L(k)=2^k(L(0)+k)\tag4 $$ which is $$ T(n)=n(T(1)+\log(n))\tag5 $$ Therefore, $T(n)=O(n\log(n))$.

Answer 4

Use the Master Theorem.