The problem
$T(n)=2T\left(\frac{n}{2}\right)+\log{n}$
$T(1)=1$
I was able to come up with the solution $\Theta{(n)}$ using Master theorem. But I want to get the same solution using expansion or I guess this is also called as substitution method. I have tried following:
$T(n)=2T\left(\frac{n}{2}\right)+\log{n}$
$=2\left[2T\left(\frac{n}{4}\right)+\log\left(\frac{n}{2}\right) \right] +\log{n}$
$=4T\left(\frac{n}{4}\right)+2\log\left(\frac{n}{2}\right)+\log{\left(n\right)}$
$=4\left[2T\left(\frac{n}{8}\right)+\log\left(\frac{n}{4}\right) \right]+2\log\left(\frac{n}{2}\right)+\log{\left(n\right)}$
$=8T\left(\frac{n}{8}\right)+4\log\left(\frac{n}{4}\right)+2\log\left(\frac{n}{2}\right)+\log{\left(n\right)}$
$=16T\left(\frac{n}{16}\right)+8\log\left(\frac{n}{8}\right)+4\log\left(\frac{n}{4}\right)+2\log\left(\frac{n}{2}\right)+\log{\left(n\right)}$
$=16T\left(\frac{n}{16}\right)
+8\left[\log\left(n\right)-\log\left(8\right)\right]
+4\left[\log\left(n\right)-\log\left(4\right)\right]
+2\left[\log\left(n\right)-\log\left(2\right)\right]
+\log{\left(n\right)}$
$=16T\left(\frac{n}{16}\right)
+8\log\left(n\right)-8\times 3
+4\log\left(n\right)-4\times 2
+2\log\left(n\right)-2\times 1
+\log{\left(n\right)}$
$=16T\left(\frac{n}{16}\right)
+\left[8\log\left(n\right)
+4\log\left(n\right)
+2\log\left(n\right)
+\log{\left(n\right)}\right]
-\left[8\times 3+4\times 2+2\times 1\right]$
The recurrence terminates at $\frac{n}{2^k}=1$. So, we can generalize this as follows:
$T(n)=2^kT\left(\frac{n}{2^k}\right) +\left[2^{k-1}\log\left(n\right) +2^{k-2}\log\left(n\right) +... +2^1\log\left(n\right) +2^0\log{\left(n\right)}\right] -\left[(2^{k-1}\times k-1)+(2^{k-2}\times k-2)+...+(2^1\times 1)+(2^0\times 0)\right] $
$T(n)=2^kT\left(1\right) +\left[(2^k-1)\log\left(n\right)\right] -\left[(2^{k-1}\times k-1)+(2^{k-2}\times k-2)+...+(2^1\times 1)+(2^0\times 0)\right] $
I am stuck here. I dont feel this is leading me to $\Theta\left(n\right)$. Is it so? Is this problem unsolvable by this approach?
(PS: I very well welcome other approaches people are suggesting in the solutions and comments. They are really really great and keep them coming. But I also want to know whether I was doing it wrong absolutely and whether it can be solved further following my path.)
If you keep on developing you get
$$ \begin{eqnarray} & & T(2^k) = 2T(2^{k-1})+k = 2\big(2T(2^{k-2})+(k-1)\big)+k = \cdots \\ & & k + 2(k-1) + 2^2(k-2)+\ldots+ 2^{k-1}\cdot 1 = \\ & & 2^k\sum_{i=1}^{k} \frac{i}{2^i} \to 2^k\cdot C \end{eqnarray} $$
for a constant $C=\sum_{i=1}^\infty \frac{i}{2^i}$ (which you can work out exactly if you care, but there is no need). So $T(2^k)=\Theta(2^k)$ and so $T(n)=\Theta(n)$.
It is always solvable by this approach because this is exactly the proof of the master theorem.