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 n0≥1 such that ∀n≥n0:
c1f(n2)≤f(n)≤c2f(n2)
Let f(n)=2n.Then:
c12n2≤2n≤c22n2⇒c1≤2n2≤c2
2n2≤c2⇒2n≤c22⇒n≤lgc22 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