0
$\begingroup$

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$

source pdf: http://www3.cs.stonybrook.edu/~algorith/video-lectures/2007/lecture2.pdf mp4: http://www3.cs.stonybrook.edu/~algorith/video-lectures/2012/CSE373_(CSE373-01)_2013_Spring_2013-01-31.html

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Mats Granvik Aug 30 '15 at 17:14
  • $\begingroup$ 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). $\endgroup$ – Asaf Karagila Aug 30 '15 at 17:19
  • $\begingroup$ @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. $\endgroup$ – wormwood Aug 30 '15 at 17:21
  • 1
    $\begingroup$ Are you anyhow familiar with limits and basic calculus? $\endgroup$ – Lonidard Aug 30 '15 at 19:15
  • $\begingroup$ @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 $\endgroup$ – Antonio Vargas Aug 30 '15 at 20:03
5
$\begingroup$

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)].

$\endgroup$
  • $\begingroup$ Note to OP: $\exists$ means "there exists" and $\forall$ means "for all". $\endgroup$ – MathMajor Aug 30 '15 at 17:19
  • $\begingroup$ @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 $\endgroup$ – wormwood Aug 30 '15 at 17:24
  • $\begingroup$ @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. $\endgroup$ – Yves Daoust Aug 30 '15 at 17:29
  • $\begingroup$ @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? $\endgroup$ – wormwood Aug 30 '15 at 17:35
  • $\begingroup$ @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. $\endgroup$ – Yves Daoust Aug 30 '15 at 18:46
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – wormwood Aug 30 '15 at 17:15
  • $\begingroup$ @wormwood, by asking to edit the question you get the equations in (LaTeX-like) text. $\endgroup$ – vonbrand Aug 30 '15 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.