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

Question

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?

score 4 · Accepted Answer · answered Apr 09 '15 at 05:05

4

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.

answered Apr 09 '15 at 05:05

Yuval Filmus

57,157

Based on the rules of big O, theta, and omega I am inclined to say that everything I listed is correct... but are they? – maregor Apr 09 '15 at 05:06
1

That's for you to figure out. – Yuval Filmus Apr 09 '15 at 05:06
A binary yes/no would be nice... If 'no' then I know I have to work it out. – maregor Apr 09 '15 at 05:09
2

You have to trust yourself more. – Yuval Filmus Apr 09 '15 at 05:09
2

Regarding $2^f$, try $f = x$ and $g = x/2$. – Yuval Filmus Apr 09 '15 at 05:10

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

1 Answers1