Showing that T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$)

Question

I am doing an exercise which says that this is true: T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$)

So I tried to solve it by substitution, but I am getting a non-sense result. So would really appreciate some pointer in the right direction.

So I want to show it for $\frac{n}{4}$ (sub-question, I am picking $\frac{n}{4}$ to show it for because the recurrence has $T(\frac{n}{4})$, but this might not be the correct way to go always?)

I substitute $T(n/4)$ for $c\sqrt{n}$ in the original equation and get

T($\frac{n}{4}$) $\leq$ 2 + 2(c $\sqrt{\frac{n}{4}}$) =

2 + 2c$\frac{\sqrt{n}}{\sqrt{4}}$ =

2+2c$\frac{\sqrt{n}}{2}$ =

2+c$\sqrt{n}$ $\leq$ c$\sqrt{n}$

Which is clearly not true.

Answer 1

Since the OP made a writing mistake in the question, I will keep the first answer and add onto it the correct one.

---

For $T(n)=2+2T(n/2):$

I believe that the recurrence relation is not $O(\sqrt{n})$, and in fact is $\Theta(n)$.

We can see this easily using the master theorem, where here $a = 2, b = 2, f(n)= 2$, and then $T(n) = aT(n/b) + f(n)$.

Since $f(n)=O(n^{\log_b (a)})=O(n)$ then by the first case in the master theorem we have $T(n) = \Theta(n^{\log_b (a)}) = \Theta(n)$.

---

For $T(n)=2+2T(n/4)$:

As I have mentioned in the previous proof, the master theorem is useful for solving such recurrence formula. In our case, we have $a=2,b=4,f(n)=2$ and thus $\log_b(a)=\log_4(2) = 0.5$

By the first case of the master theorem, since $f(n)=O(n^{\log_b(a)})=O(n^{0.5})=O(\sqrt n)$ then we will also have $T(n) = \Theta(\sqrt n)$