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

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

Your counter-example isn't true.

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

  • $\begingroup$ Thanks! I didn't thought about making n a power of something. :) $\endgroup$ Jul 25 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.