Monday 20 February 2017

asymptotics - Prove or disapprove the statement: $f(n)=Theta(f(frac{n}{2}))$



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?


Answer



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


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...