How to solve the following recursive formula?

108 Views Asked by At

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)$

1

There are 1 best solutions below

2
On BEST ANSWER

$$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$$