3

Prove or disprove with counter example:
$$O(f(n)\cdot g(n)) = f(n)\cdot O(g(n))$$

Attempt:
$f(n) = x^2 + x + 1$
$g(n) = x^3$
L.H.S. = $x^5$
R.H.S. = $(x^2 + x + 1)x^3$
L.H.S. $\neq$ R.H.S.

Am i correct?

kayush
  • 2,441
  • This is a property of Big-O notation, listed here. – Minus One-Twelfth Feb 20 '19 at 06:06
  • Can you tell me what i did wrong in my example? – kayush Feb 20 '19 at 06:06
  • 1
    @kayush The $O$ notation doesn't denote exact functions, but rather an order of magnitude. Thus, for example, $O\left(f\left(x\right)\right) = O\left(g\left(x\right)\right)$ doesn't necessarily mean that $f\left(x\right) = g\left(x\right)$. – John Omielan Feb 20 '19 at 06:18
  • @JohnOmielan i know, have i used this anywhere in my attempt? – kayush Feb 20 '19 at 06:25
  • 1
    @kayush Yes, you did implicitly in your statement for R.H.S. The value of $O\left(g\left(x\right)\right)$ is not necessarily $g\left(x\right) = x^3$. – John Omielan Feb 20 '19 at 06:28
  • Thanks, but how to approach such problems? – kayush Feb 20 '19 at 06:37
  • per definition. it is an equality between sets. so for the first direction let h(x) be in O(fg). that means h(x) <= cf(x)g(x). we have to show that h is in fO(g) rearranging leads to h(x) <= f(x)(cg(x)), so h is in f*O(g). i guess you can see the second direction out of this one. – Luke Feb 20 '19 at 08:42

0 Answers0