Solve the recurrence relation

Question

Assuming that $n$ is a power of $2$, solve the recurrence relation $$T(n)=2T\left(\frac{n}{2}\right)+2$$ Take $T(2)=1$ and $T(1)=0$.

Also how can this be done with the master theorem, if possible?

Answer 1

This is standard question solved by the Master Theorem. Using the same notation as http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem.pdf we have that $a=1$, $b=2$ and $d=0$ (since $f(n)=2$ is a constant function). Because $a=b^d$ it means that this recurrence relation falls in case 2.

So, $T(n) = Θ(n^0\log{n})=Θ(\log{n})$