Question: $T(n) = 2T(n/2) + n$ ==> Note our result will be $\Theta$(nlog(n))
The very first step you should take is putting everything in the form $T(n)=b^np^n$ so $T(n) - 2T(n/2) = n$
Because this is an inhomogenous relation, we want to turn it into a solvable homogenous problem.
Note we can treat n as 2^k becasue of the bn property.
So now we have $T(2^k) - 2T({2^k}/2) = 2^k$
Next, we multiple both sides by 2 to get the k+1 condition, so $2T(2^k)-4T(2^{k-1}) = 2^{k+1}$
Then we can have a duplicate of the above term, except write it in terms of k+1 so $T(2^{k+1})-2(T^k)= 2^{k+1} $
And then subtract the two terms $T(2^{k+1})-2(T^k)= 2^{k+1} - 2T(2^k)-4T(2^{k-1}) = 2^{k+1}$
to get: $T(2^{k+1})-4T(2^k)-4T(2^{k-1}) = 0$
Next we can rewrite $T(2^k)$ as $X^p$
so,
$X^{p+1} -4X^P -4X^{p-1} = 0$
...
So on $(X^{p-1})(X^2-4X-4)= 0$ //Ignore the first part//
so, $X^2-4X-4=0$ and our roots become x=2,2
Because the roots are not distinct, we use the formula, $\sum c_ir^{p}p^{i-1}$
which brings us to $(2)^p + 2^{p}*(p)$
which $p = 2^k$ and $2^k = n$
and so $2^{2^k}+2^{2^k}(2^k)$ which should be $2^{n}+2^{n}*n$ ...
But my professor treats $\sum c_ir^{p}p^{i-1}$ the $p^{i-1}$ as a separate value of just K not $2^k$ in which then K = log(n) ... why is this?
Considering for $n \in \mathbb{N}_{>0}$
$$ T(2^{\log_2 n}) = 2T(2^{\log_2(\frac n2)})+n $$
calling now $T'(u) = T(2^u)$ we have
$$ T'(\log_2 n) = 2T'(\log_2 n - 1) + n $$
and calling now $u = \log_2 n$ we have
$$ T'(u) = 2T'(u-1)+2^u $$
which is a linear recurrence with solution given by
$$ T'(u) = T'_h(u) + T'_p(u)\\ T'_h(u) = 2T'_h(u-1)\\ T'_p(u) = 2T'_p(u-1)+2^u $$
so we have
$$ T'_h(u) = C 2^{u-1} $$
now making $T'_p(u) = C(u) 2^{u-1}$ and substituting into the particular recurrence we obtain the new recurrence
$$ C(u)-C(u-1) = 2\Rightarrow C(u) = 2u $$
so
$$ T'(u) = \left(C+2u \right) 2^{u-1} $$
hence
$$ T(n) = C_1n+n\log_2 n $$