# Proving upper/lower bound

$$f (n) = Θ(f (n/2))$$

The counter example in the solutions was $$f(n)=\sqrt{n}$$.

But then we get for every $$n\ge n_{0}$$

$$\sqrt{n}\le c_{0}\sqrt{\frac{n}{2}}\ \ ->\ \ n\le c_{0}^{2}\cdot\frac{n}{2}\ \ \ ->\ \ 2n\le c_{0}^{2}\cdot n\ \ ->\ 2\le c_{0}^{2}$$

and I don't see a problem with that, as we can choose $$c_{0}=2$$. Same with the omega definition. So what am I missing?

• In your reasonings you missed nothing, of course $\sqrt{n}\in \Theta(\sqrt{n/2})=\Theta(\sqrt{n})$. Jul 24 at 17:04
• Thanks, this is probably a mistake in their solutions. Jul 25 at 6:32

Let $$f(n)=2^n$$, we see that $$f(\frac{n}{2})=2^\frac{n}{2}=\sqrt{2}^n.$$
As a result we show that $$f(n)\neq\Theta(f(\frac{n}{2}))$$ $$\lim_{n\to \infty}\frac{f(n)}{f(\frac{n}{2})}=\frac{2^n}{\sqrt{2}^n}$$ $$=\frac{2}{\sqrt{2}}\times\dots\times\frac{2}{\sqrt{2}}$$ $$=\frac{\sqrt{2}}{1}\times\dots\times\frac{\sqrt{2}}{1}$$ $$=\frac{\sqrt{2}^n}{1}=\infty.$$ So, $$f(n)\neq\Theta(f(\frac{n}{2}))$$.