I am very new to recursion and have no idea how to solve the following problem.
$n \geq 1$ is a power of 2 integer
$T(1) = 0$
$T(n) = 2T(\frac{n}{2}) + n$
Can someone please explain to me how to do this? If you can kindly work it as example, I will be able to do the other problems. Thanks. Below is what I attempted
Using the master theorem
$a = 2$ $b = 2$ $d = 1$
$d = log_2 2 $
Hence my answer is $\Theta(n\log n)$
$$T(n) = 2(2T(\frac{n}{4}) + \frac{n}{2}) + n = 2^2 T(\frac{n}{4}) + 2n $$
By expanding the equation you can get: $$T(n) = 2^nT(1) + n\times(\log(n)-1) = n\log(n) - n$$