I have to prove or disprove this: If ${f(n)}=O(g(n))$, prove/disprove ${(f(n))^3} = O (g(n))^3 )$. From what we are given: ${f(n)}<=C_1g(n)$ for some constant $C_1$. Now I have to show that ${(f(n))^3} <= C_2(g(n))^3 )$. My intuition says that we should be able to find a constant $C_2$ and that $C_2 = C_1^3$. Is this wrong? If wrong, what would be the right way to think about it? Thanks.
Asked
Active
Viewed 211 times
0
-
Do you know - is $f(n)$ non negative? – zkutch Sep 20 '20 at 02:53
-
no, can be negative or positive – aky Sep 20 '20 at 03:25
-
Then there from definition should be $|f| \leqslant C |g|$ and your suggestion about $C^3$ is correct conclusion. – zkutch Sep 20 '20 at 03:33