6
$\begingroup$

Prove or disapprove the statement:

$$f(n)=\Theta(f(\frac{n}{2}))$$

where $f$ is an asymptotically positive function.

I have thought the following:

Let $f(n)=\Theta(f(\frac{n}{2}))$.Then $\exists c_1,c_2>0 \text{ and } n_0 \geq 1 \text{ such that } \forall n \geq n_0:$

$$c_1 f(\frac{n}{2}) \leq f(n) \leq c_2 f(\frac{n}{2})$$

Let $f(n)=2^n$.Then:

$$c_1 2^{\frac{n}{2}} \leq 2^n \leq c_2 2^{\frac{n}{2}} \Rightarrow c_1 \leq 2^{\frac{n}{2}} \leq c_2 $$

$$2^{\frac{n}{2}} \leq c_2 \Rightarrow 2^n \leq c_2^2 \Rightarrow n \leq \lg c_2^2 \text{ Contradiction}$$

Could you tell me if it is right?

$\endgroup$
  • 3
    $\begingroup$ It's true for some functions but not for others. Your counterexample is perfect. $\endgroup$ – Antonio Vargas Jul 13 '14 at 18:48
  • $\begingroup$ Great!!!Thank you very much!!! $\endgroup$ – evinda Jul 13 '14 at 18:51
  • 2
    $\begingroup$ In the future just use the (asymptotics) tag. No need for the "big-o-notation" tag. $\endgroup$ – Antonio Vargas Jul 14 '14 at 6:24
  • $\begingroup$ @AntonioVargas A ok!!!I will take it into consideration!!! :) $\endgroup$ – evinda Jul 14 '14 at 14:32
4
$\begingroup$

As mentioned in the comments, your work is correct (and thus the original proposition is false).

$\endgroup$
1
$\begingroup$

Just set $f=f(n) = 2^{\frac{n}{2}}, \ g=g(n) = 2^n$ and take $\lim_n \frac{f}{g} = 0$, so $f <c_1 g \ \forall \ c_1>0 $ and $n>n_0$ or simply $f=o(g)$. Clearly $\lim_n \frac{g}{f} = \infty$, so LHS of the inequality is never fulfilled: $\not \exists c_2 \ \text{s.t.} f>c_2g \ \forall n>n_0$ or simply $g=\omega(f)$.

$\endgroup$

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.