1
$\begingroup$

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

Big O definition

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:

enter image description here

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.

$\endgroup$
3
  • $\begingroup$ Does this answer your question? Analysis of algorithms, 'big O' question $\endgroup$
    – Pål GD
    Dec 1 '21 at 8:28
  • $\begingroup$ The answer to the third question is a bit weird. It correctly says "No", but the explanation after "because" is not a proof that the answer is "no". $\endgroup$
    – Stef
    Dec 1 '21 at 11:38
  • 1
    $\begingroup$ Right, @Stef. I wrote about it in my answer. $\endgroup$
    – zkutch
    Dec 1 '21 at 16:22
1
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ I think you meant $f(n) < c\cdot g(n)$. $\endgroup$
    – Pseudonym
    Dec 1 '21 at 1:59
  • 1
    $\begingroup$ In negation? If yes, then we take negation of $f(n) \leqslant c \cdot g(n)$ from definition on last step. $\endgroup$
    – zkutch
    Dec 1 '21 at 2:14
  • $\begingroup$ Oh, sorry, my mistake. I misread that completely. As you were! $\endgroup$
    – Pseudonym
    Dec 1 '21 at 2:23
1
$\begingroup$

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

$\endgroup$
1
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.