Merge Sort time complexity analysis How can I prove that $T(n) = 2T(n/2) + n$ is $O(n \log n)$ ?
 A: 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.
A: 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))$.
A: T(1) = 1 
T(n) = 2T (n/2) + cn 
T(n) = 2T (n/2) + cn
T(n/2) = 2T(n/4) + c (n/2)
T(n) = 2 [ 2T (n/4) + c (n/2) ] + cn
T(n) = 4T (n/4) + 2cn
Similary, 
T(n) = 8T (n/8) + 3cn 
General 
T(n) = 2^k T (n/2^K) + kcn
(n/2^k) = 1
n = 2^k
k = log base2 n
plug in k into the general formula
T(n) = n T(1) + logBase2n cn 
T(n) = Big Thetha(n log n )
A: 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.
A: Use the  Master Theorem.
