# prerequisit for BigO notation

I have been trying to learn algorithms for a long time now and I am really struggling with the math part and don't know what to do. I only know very basic math, so my question is what do I have to know to be able to understand BigO notation? For example,

$f(n) = O(g(n))$ if there are positive constants $n_0$ and $c$ such that to the right of $n_0$, the value of $f(n)$ always lies on or below $c\cdot g(n)$.

Big Oh Examples
$3n^2 - 100n + 6 = O(n^2)$ because $3n^2 > 3n^2+ 100n + 6$
$3n^2 - 100n + 6 = O(n^3)$ because :$n^3 > 3n^2 - 100n + 6$
$3n^2 - 100n + 6 6= O(n)$ because $c \cdot n < 3n^2$ when $n > c$

I am totally lost. What should I do to learn this? And I would be greatful if someone explain what it means.

• If I remember correctly, correct me if I am wrong, O(expression) means that there exists a constant "c" such that the absolute value of your function is bounded by "c" times "expression". Example: O(n^2) means that there exists a constant c such that: Abs(3*n^2-100*n +6) < c*n^2 – Mats Granvik Aug 30 '15 at 17:14
• It seems to me that there are some powers that are missing and that makes the question somewhat less readable (e.g. $n2$ should be $n^2$, I guess). – Asaf Karagila Aug 30 '15 at 17:19
• @Asaf Karagila I'm sorry about that. I wrote them as text because my screen reader would not read them if I did not write them as text. But I provided the link to the source. – wormwood Aug 30 '15 at 17:21
• Are you anyhow familiar with limits and basic calculus? – Lonidard Aug 30 '15 at 19:15
• @wormwood, you may be interested in looking at the Math Player plugin for Internet Explorer, which can apparently vocalize the formulas displayed on this site. I personally wasn't able to get it working, but it is widely used, so maybe I'm just doing something wrong. Here's a link – Antonio Vargas Aug 30 '15 at 20:03

The big $O$ [O] notation is there to express the growth rate of a function (the running time of an algorithm) in a simple way, abstracting away unnecessary details. This growth rate is an essential factor in judging the useability of the algorithm.

In particular, if you look at the behavior of a polynomial like $T(n)=3n^2-100n+6$ [T(n)=3n²-100n+6], it has three terms each with a different growth rate. If you plot them, you will notice that the higher degree term dominates the others for sufficiently large $n$ [n].

For this reason, we like to say that $P(n)$ [P(n)] grows like $n^2$ [n²]. We don't care about the low order terms (for high $n$ [n] they become neglectible), nor do we care about the coefficient of $n^2$ [n²] (it does not influence the growth rate).

In computer science, we often work with upper bounds, as the running time of algorithms is rarely a function of $n$ [n] alone (it also depends on the input data values); to work around this, instead of dealing with the exact running time, it is customary to work with a function guaranteed to be larger than the running time in all cases.

These two ideas put together (growth rate of the upper bound) are formalized by the big-$O$ [O] notation: we want to find a function $g(n)$ [g(n)] that is larger than $f(n)$ [f(n)] for sufficiently large $n$ [n], with a multiplicative constant allowed:

$$f(n)\in O(g(n))\iff\exists\ n_0, c: \forall n\ge n_0: f(n)\le c\cdot g(n).$$

[f(n) is in O(g(n)) iff there exists n0, c such that for all n >= n0, f(n)<= c.g(n)].

For a given function $f(n)$ [f(n)], if you want to prove that $f(n)\in O(g(n))$ [f(n) is in O(g(n))] for some candidate growth rate $g(n)$ [g(n)], you need to find $n_0$ [n0] and $c$ [c] that fulfill the condition.

Now you should be able to check for yourself that $T(n)\in O(n^3), T(n)\in O(n^2)$ [T(n) is in O(n³), T(n) is in O(n²)] and $T(n)\notin O(n)$ [T(n) is not in O(n)].

• Note to OP: $\exists$ means "there exists" and $\forall$ means "for all". – MathMajor Aug 30 '15 at 17:19
• @Yves Daoust I am using a screading software. Do you mind turning the equations into text? And can you help me understand the big O examples in my question? Thanks – wormwood Aug 30 '15 at 17:24
• @wormwood: mh, if my explanations do not allow you to process the examples, I failed and you'd better wait for someone else's answer. – Yves Daoust Aug 30 '15 at 17:29
• @Yves Daoust I mean my screen reading software can't read your equations so I can't understand them. For example, my screen reader read one of your sentence as: "In particular, if you look at the behavior of a polynomial like , it has three terms each with a different growth rate". After "polynomial like " and before ", " I'm sure there is an equation there. Do you mind tunring them into text/characters? – wormwood Aug 30 '15 at 17:35
• @wormwood: I have added a transliteration of every formula following them, between square brackets. I have used the "exponent 2" character several times and "exponent 3" once. If your screen reader doesn't render them, let me know. – Yves Daoust Aug 30 '15 at 18:46

One almost equivalent way to understand big-O is if $f(x)/g(x)$ becomes closer and closer to a non-negative constant (even zero) as $x$ grows then $f(x) = O(g(x))$. Thus it means they either have the same fundamental growth rate, or $g(x)$ has a fundamentally faster growth rate (in the case that $f(x)/g(x)$ becomes closer and closer to zero). But in terms of $f(x)/g(x)$, as long as you can show that it's less than some positive constant for $x$ large enough, this is the exactly the same as big-O.

In computer science, the reason why we use big-O is that we want to express the fundamental growth rate of the running time or space used of an algorithm/program, in terms of the size $x$ of the input, without worrying about details about whether one CPU operation takes twice as long as some other operation, or whether the true growth rate of algorithm running time/space is different in an additive way that becomes less and less important as $x$ increases. We want a very simple expression (like $O(n^3)$) that captures the "essence" of the running time. We don't mind if the actual running time is say, 10 times longer as $x$ grows, just as long as it's only a bounded constant factor multiplier as $x$ grows. As long as the constant is not too large, we can get pretty good ideas about how large on an input we can handle if we know the big-O.

One way to approach big-O in practice when doing calculations is by memorizing some general rules (assuming you understand the rough concept of what big-O means):

If $f(x) = O(g(x))$ and $h(x)$ is an increasing function, then $h(f(x)) = O(h(g(x)))$ and $f(h(x)) = O(g(h(x)))$.

If you are given a weighted sum of $k$ functions $c_1f_1(x) + c_2f_2(x) + c_3f_3(x) + \ldots c_kf_k(x)$ and each function $f_i = O(g(x))$ then the sum is also $O(g(x))$.

If $f_1(x) = O(g_1(x))$ and $f_2(x) = O(g_2(x))$ for positive $f_1,f_2$, then $f_1(x) \cdot f_2(x) = O(g_1(x) \cdot g_2(x))$

$x^c = O(a^x)$ for any $c$ and any $a > 1$.

$(\log x)^c = O(x^d)$ for any $c, d > 0$.

The last two are important in certain cases, and can be shown by L'Hopital's rule.

• I am using a screading software. Do you mind turning the equations into text? And can you help me understand the big O examples in my question? Thanks – wormwood Aug 30 '15 at 17:15
• @wormwood, by asking to edit the question you get the equations in (LaTeX-like) text. – vonbrand Aug 30 '15 at 17:21