0
$\begingroup$

If for functions $f, g$ we have $f = \mathcal{O}(g)$, then does $g = \mathcal{O}(f)?$ Explain why this is true or give an example showing it is false.

Workings:

I believe this is false. if I take $g = n^3 +20 n +1$ then $f = \mathcal{O}(g) = \mathcal{n^3}$

But $g = \mathcal{n^3} = n^3 \neq n^3 +20n +1$

Is what I said correct? Any help will be appreciated.

$\endgroup$

1 Answer 1

2
$\begingroup$

Your stated belief is correct but your example isn't.

You should think of $\mathcal{O}$ as "grows no faster than (asymptotically)". Thus

$$ n^3 + 20n +1 = \mathcal{O}(n^3) $$ and $$ n^3 = \mathcal{O}(n^3+ 20n +1) $$ and $$ n = \mathcal{O}(n^3) $$ but $$ n^3 \ne \mathcal{O}(n). $$

Note: this isn't the formal definition of $\mathcal{O}$ but it is a good way to train your intuition.

$\endgroup$
1
  • $\begingroup$ Ok I see. Thanks! $\endgroup$ Oct 2, 2016 at 19:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .