Having a lot of trouble trying to reason the formal definition of Big O

Question

My professor recently brushed over the formal definition of Big O:

To be completely honest even after him explaining it to a few different students we all seem to still not understand it at its core. The problems in comprehension mostly occurred with the following examples we went through:

So far my reasoning is as follows:

When you multiply a function's highest term by a constant, you get a new function that eventually surpasses the initial function at a given n. He called this n a "witness" to the function O(g(n))

How is this c term created/found? He mentioned bounds a couple of times but didn't really specify what bounds signify or how to find them/use them.

I think I just need a more solid foundation of the formal definition and how these examples back up the definition.

Answer 1

How is this c term created/found?

Answer is individual to each example. Let's take Your first one $f(n)=n^2+3n$ and $g(n)=n^2$. We need constants to satisfy inequality $$n^2+3n \lt c \cdot n^2$$ simplification gives $n \gt \frac{3}{c-1}$. I hope you easily found infinity couples of $n_0,c$ for which inequality is true.

Let me, also, help you with 3'd example assuming, that base of $\log$ is more $1$. Proving, that some function is $O(n\log n)$ doesn't mean, that it is not in $O(n)$. More: we have $O(n) \subset O(n\log n)$, so, each function from $O(n)$ is also in $O(n\log n)$.

To prove directly, that some function is not in some big-$O$, you need negation of definition $f(n)\in O(g(n)),n\to\infty$:

$$\forall c >0, \forall n_0\in\mathbb{N}, \exists n>n_0, f(n)>c\cdot g(n) $$

Taking now $f(n)=n\log n+2n$ and $g(n)=n$ we need to prove $n\log n+2n>c\cdot n$. After simplification we obtain $\log n > c-2$. This inequality, in required conditions, comes from $\lim\log n=+\infty$.

Answer 2

Adding another note to the already great answers.

A source of possible confusion might be from the notation surrounding this concept. The equals sign used in the statement$\ f(x) = O(g(x))$ is not meant to indicate an equality relation but instead should be interpreted as set membership. There are plenty of explanations made by much more informed people than me, including this math stack exchange question and throughout various parts of this wikipedia article.

For a formalization of the concept read the beginning of this paper. To put it briefly though,$\ O(g)$ is a set of functions and $\ f(x) = O(g(x))$ should be interpreted as saying $\ f \in O(g)$. In the context with which you are learning about it,$\ O(g(x))$ can be intuitively thought of as a class of functions that share the property of having a growth rate that is equal to or less than$\ g(x)$.

Answer 3

Look no further than the picture you attached that say

$f(n)$ is $O(g(n))$ if there exist two positive constants $c$ and $n_0$ such that $f(n) \leq c \cdot g(n)$ for all $n > n_0$.

That's the full formal definition and foundation for the O notation.

Sit down and prove that $n^2$ is not $O(n)$.

Answer 4

This is an addendum to the other answers, which are very good.

The formal definition is important, but intuition comes from concrete examples. If you think about why we use asymptotic notation for, say, the time that an algorithm takes to run in the worst case, it's because the actual time may depend on a bunch of factors not in your control, such as how good your compiler is, how many other programs are running on the same machine, CPU clock speed, etc.

When analysing the run-time of algorithms, the constant $c$ "comes from" all of that.

This isn't the only use for big-oh notation, of course; if you learn numeric analysis, it will be used for other purposes, such as truncating power series. But this is one of the most common that you will see.

You haven't gotten to little-oh notation, yet, but here's something that might help.

$f(n)$ is $O\left(g(n)\right)$ if there exists a $c$, such that there exists a $n_0$, such that for all $n>n_0$, $f(n) < c\cdot g(n)$

$f(n)$ is $o\left(g(n)\right)$ if for all $c$, there exists a $n_0$, such that for all $n>n_0$, $f(n) < c\cdot g(n)$

The difference between big-oh and little-oh is that with big-oh, the constant is chosen for you, and with little-oh, you choose the constant and therefore it can be as small as you like. (This is why when discussing little-oh notation, $c$ is often spelled $\varepsilon$.)