\(T(1) = 0\)
\(T(n) = 2T(\frac{n}{2}) +\theta(log(n))\)
\(\Theta(n)\)
Let \(n = 2^k,\ k \in \ Integer\)
The Recurrence can be expressed as:
\(log(n)+2^1log(\frac{n}{2})+2^2log(\frac{n}{2^2})+...+ 2^{k-1}log(\frac{n}{2^{k-1}})\)
\(=log(n)+log(\frac{n}{2})^2+log(\frac{n}{2^2})^{2^2}+...+ log(\frac{n}{2^{k-1}})^{2^{k-1}}\)
\(=C(log_2(n)+log_2(\frac{n}{2})^2+log_2(\frac{n}{2^2})^{2^2}+...+ log_2(\frac{n}{2^{k-1}})^{2^{k-1}}), \ C\ \) is a const
\(\simeq log_2(n\times n^2\times n^{2^2}\times...\times n^{2^{k-1}}) -(2+2\times2^2+3\times2^3+...+(k-1)\times2^{k-1})\)
\(log_2(n\times n^2\times n^{2^2}\times...\times n^{2^{k-1}})\)
\(= log_2(n^{1+2+2^2+...+2^{k-1}})\)
\(= log_2(n^{2^k-1})\), combined with \(n = 2^k\)
\(= log_2(n^{n-1})\)
\(= n\times log_2(n) -log_2(n)\)
Let \(S=2+2\times2^2+3\times2^3+...+(k-1)\times2^{k-1}\) \[ \begin{align} S&=2+2\times2^2+3\times2^3+...+(k-1)\times2^{k-1} \\ 2S &=0+1\times2^2+2\times2^3+...+(k-2)\times2^{k-1}+(k-1)\times2^{k-1} \end{align} \] Therefore, \(S=-(2+2^2+2^3+...+2^{k-1})+(k-1)\times2^k\)
\(=-(2^k-2)+(k-1)\times2^k\)
\(=(k-2)\times2^k+2\), combined with \(n = 2^k, \ k=log_2(n)\)
\(=(log_2(n)-2)\times n + 2\)
\(= n\times log_2(n)- 2\times n + 2\)
The Recurrence
\(=(first \ term)-(second \ term)\)
\(=(n\times log_2(n) -log_2(n)) - (n\times log_2(n)- 2\times n + 2)\)
\(= 2\times n - log_2(n) - 2\)
\(\sim \Theta(n)\)