4

So I have this is an assignment for algorithms. I've googled a lot, read the chapter in the book about big Oh notation, and I understand the concept. I do not however understand how to prove it. I know I need to work with a constant and put that out of the equation. And I know that the answer I've found for $f(n) = O(g(n))$ implies $g(n) = O(f(n))$ is

NO. $f(x)=x$,$g(x)=x^2$ is a counterexample.

But I do not understand this answer. If $g(x)$ could be $x^2$ then $f(n)$ would not be equal the $O(g(n))$.

Can someone explain in a simple way why this is the case though? :(

NicklasN
  • 141

2 Answers2

3

The definition of the big-oh notation is as follows :

$f(x)=O(g(x))$ if $|f(x)| \leq c|g(x)|$ for every big enough $x$ and some constant $c$

This is why $f(x)=x$ and $g(x)=x^2$ is a counter-example :

  • $x=O(x^2)$ because for example taking $c=1$ we have $x \leq x^2$ for every $x \geq 1$

  • $x^2$ can't be $O(x)$ because that would mean that $x^2 \leq cx$ for every $x \geq x_0$ or $x^2-cx \leq 0$ but this is false because : $$\lim_{x \to \infty} x^2-cx=\infty$$

The usual intuition is that :

$f(x)=O(g(x))$ when $g(x)$ grows faster than $f(x)$

This explains why $x=O(x^2)$ but the reverse isn't true .

  • Thank you for your reply. I still do not understand it, I've read the definition several places and times. I'm having difficulties understand it because I cannot put it in context.

    So f(x) = O(g(x)) means that g(x) grows faster than f(x) but shouldnt it be opposite? If f(x) = O(g(x)) then f(x) is faster growing than g(x) since O(g(x)) is worst case scenario?

     – NicklasN Feb 05 '16 at 08:52
  • @NicklasN Maybe you can tell us specifically what you don't understand and we will help you . –  Feb 05 '16 at 08:54
  • Yes sorry, I forgot that enter did not skip line, but added the comment.. I have edited the comment above :) – NicklasN Feb 05 '16 at 08:55
  • @NicklasN Because $O(g(x))$ is something that grows slower than $g(x)$ when I write $f(x)=O(g(x))$ I practically say that $f(x)$ grows slower than $g(x)$ –  Feb 05 '16 at 08:59
  • 1
    Oh yes ofcourse, by saying that you say that it takes more time for the algorithm, which is true. It grows slower. O(f(x)) is slower than O(g(x)), so it does not imply that g(x) = O(f(x)), since that is impossible.. is this understood correctly? – NicklasN Feb 05 '16 at 09:45
  • @NicklasN Yes, Because if $f(x)$ grows slower than $g(x)$ it doesn't necessarily follows that $g(x)$ grows slower than $f(x)$ ,as in the example $f(x)=x$ and $g(x)=x^2$ . But there are examples when both $f(x)=O(g(x))$ and $g(x)=O(f(x))$ hold .For example you can take $f(x)=x$ and $g(x)=x+2$ . –  Feb 05 '16 at 09:51
  • So if we set $f(x)$ to 2, and $g(x)$ to $2^2$, then 2 would grow as slow as $2^2$, but now slower. However $2^2$ would not grow as slow as 2 since.. I have trouble proving why this is .. This specific case. – NicklasN Feb 05 '16 at 09:56
  • Let us continue this discussion in chat. –  Feb 05 '16 at 10:12
  • The best solution I have seen so far. Thank you. – Avv Aug 08 '21 at 23:35
1

Recall the definition of $g = O(f)$:

We say that $g = O(f)$ iff there are $c \ge 0$ and $N \in \mathbf N$ such that $$\def\abs#1{\left|#1\right|}\abs{g(n)} \le c\abs{f(n)}, \quad n \ge N. $$

Suppose now $f(n) = n$ and $g(n) = n^2$, we would have to show that $$ n^2 \le cn $$ is true for "$n$ large" and some $c$. But regardless of which $c$ we choose, if $n$ is larger this does not hold (note that $c$ has to be fixed). Hence $g \ne O(f)$.

martini
  • 84,101