prerequisit for BigO notation

Question

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.

Answer 1

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.

Answer 2

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