0

I read the definition that $f$ is in $O(x^n)$ if $|f(x)|<C|x^n|$ for some $C$.

I'm struggling to understand how to check this. For example, supposedly $f(x) = 5x+3x^2$ is in $O(x)$ but not $O(x^2)$?

If I plot $f(x) = 5x + 3x^2$ and $g(x)=x$ I see that the first goes to infinity much quicker.

enter image description here

If I let $g(x) = Cx$, and plot $C=1,C=10, C=20, C=100$, it looks like it overcomes $f$ for $C>10$: enter image description here

But, if you zoom out further, you can see that's not true:

enter image description here

So, I know it doesn't matter what $C$ is, but how can I show that there exists a $C$ to make the definition hold so that I can tell if $f$ is in $O(x^n)$?

If you go out far enough, and $C$ is large enough can't I make either $f$ or $g$ as close to the y-axis as I want?

user17753
  • 414

2 Answers2

1

The definition is not complete since the inequality is supposed to hold for all $x>k$ where $k$ is a constant. The idea behind the $\mathcal O$-notation is to provide an estimate (comparison) for large $x$. This makes life much easier for your example since $x < x^2 \ \forall\, x>1$, so that

$0<f(x)= 5x+3x^2<5x^2+3x^2=8x^2 \ \forall \, x>1$

So you might choose $C:=8$ and $k:=2$ here in order to see that $f\in\mathcal O(x^2)$. By the way, this statement can be generalized to hold for polynomials of degree $n$, i.e. if $f\in \mathcal P_n$ then $f\in\mathcal O(x^n)$.

Dr_Be
  • 180
0

The function $f(x) = 5x + 3x^{2} \not \in O(x)$, but it is in $O(x^{2})$. The way you show that $f(x) \in O(x^{2})$ is by picking a constant $C$ and appropriate constant $k$ such that $|f(x)| \leq Cx^{2}$ for all $x \geq k$.

Big-O can often be ascertained using limits. If the following condition holds:

$$L = \lim_{x \to \infty} \dfrac{f(x)}{g(x)} < \infty$$

Then we have that $f(x) \in O(g(x))$. The converse does not necessarily hold, as given in the comments below ($x*sin(x)$).

So consider:

$$\lim_{x \to \infty} \dfrac{5x + 3x^{2}}{x} = 5 + \lim_{x \to \infty} 3x = \infty$$

And:

$$\lim_{x \to \infty} \dfrac{5x + 3x^{2}}{x^{2}} = 0 + 3 = 3$$

Thus, $f(x) \in O(x^{2})$ but not $O(x)$.

You can check out these links for more information on how to formulate Big-O proofs: http://www.dreamincode.net/forums/topic/280815-introduction-to-proofs-induction-and-big-o/ http://www.dreamincode.net/forums/topic/321402-introduction-to-computational-complexity/

ml0105
  • 14,674
  • So this is taking the ratio of the functions as $x\to\infty$ and seeing which one "wins", and if $g$ wins then $f$ is in $O(g(x))$. – user17753 Jan 12 '16 at 16:07
  • Also, if instead of $x\to\infty$, if we look at $x\to0$ then the reverse is true? So the inequality is reversed? – user17753 Jan 12 '16 at 16:11
  • Not really. The "reverse" as you might call it of Big-O is Big-Omega: $f(x) \in \Omega(g(x))$ iff there exist positive constants $C, k$ such that $|f(x)| \geq C * |g(x)|$ for all $x \geq k$. We again take the limit as $x \to \infty$. If this limit is greater than $0$, we have that $f(x) \in \Omega(g(x))$. – ml0105 Jan 12 '16 at 16:28
  • One more question... what if the limit does not exist? – user17753 Jan 12 '16 at 16:33
  • Then you can't make a claim about the asymptotics. These concepts are used in computer science and math to talk about resource usage of algorithms, growth of functions, etc. I've never run into this problem in the context in which it is used. – ml0105 Jan 12 '16 at 16:35
  • 2
    @user17753: Sorry to disturb this old post but I just happened across it. Unfortunately, this answer is incorrect. The definition using limits given here is wrong. $\limsup$ is not the same as $\lim$. For example, $x \sin(x) \in O(x)$ as $x \to \infty$, even though certainly the limit does not exist. Also, very frequently in CS, an algorithm is given for which we can only prove upper bounds on time complexity, which can be expressed using Big-O notation, and which does not imply existence of any limit. ml0105: I'll upvote if you fix your post; feel free to ask if you're not sure. – user21820 Oct 08 '16 at 03:47
  • That's a good catch! Thanks for letting me know! I've fixed my post. – ml0105 Oct 08 '16 at 16:29