Using $f=O(g)$ to compare $f^2$ and $g^2$

151 Views Asked by At

When we have $f = O(g)$, does this work? $f^2 = O(g^2)$? If I have $n^2 = O(n^3)$, I think that $n^4= O(n^6)$ so I think this is valid. What about $2^f vs 2^g$? Does $f = O(g)$ imply $2^f = O(2^g)$?

And also can I do this? if $f = θ(g)$, is $f^2 = θ(g^2)$? and if $f = Ω(g)$, is $f^2 = Ω(g^2)$? Is there some general rule that I can follow?

1

There are 1 best solutions below

5
On BEST ANSWER

There are no rules. Use the definition. For example, $f = O(g)$ means that there exist $C,X$ such that for $x > X$ we have $f(x) < Cg(x)$. If we square this then we get that for $x > X$, $f(x)^2 < C^2 g(x)^2$, and so $f^2 = O(g^2)$. See if you can replicate this thinking for your other questions.