Monday, 20 February 2017

asymptotics - Prove or disapprove the statement: f(n)=Theta(f(fracn2))



Prove or disapprove the statement:



f(n)=Θ(f(n2))



where f is an asymptotically positive function.




I have thought the following:



Let f(n)=Θ(f(n2)).Then c1,c2>0 and n01 such that nn0:



c1f(n2)f(n)c2f(n2)



Let f(n)=2n.Then:



c12n22nc22n2c12n2c2




2n2c22nc22nlgc22 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 limhrightarrow0fracsin(ha)h

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