Understanding the O-Notation

2024-11-07

During the lectures, O-notations appear everywhere, but I never got the hang of it.

It sounds like you didn't review your Data Structures and Algorithms lecture.

Yeah, but I wouldn't be asking you if I wanted to, would I?

...Fair enough.

Imagine you wrote a piece of code:

TypeScript
function hellO() {
    console.log("Hello World!");
}

and you want to see how fast it is. You could let it run multiple times and measure the average time it took in miliseconds, but would your piece of code take the same amount of time in another computer?

Well, that depends. If it has a much better processor, then it'd probably take much less time to run it.

Exactly. We therefore need a unit independent from seconds in order to measure the runtime.

Another issue occurs when the function has an input:

TypeScript
function hellO(n: number) {
    for (let i = 0; i < n; i++) {
        console.log("Hello World!");
    }
}

Unlike the first example, the runtime of this function depends on the input number. If we assume the console.log("Hello World!") part takes a constant time of $c$, then the runtime of the function would be around $c \cdot n$. In this case, we say the function above has a linear runtime.

Okay, but I still don't get why we need the O-notation.

Well, the O-notation helps us to formally group programs with similar runtime behavior into the same box, known as complexity classes. Suppose we want to group all programs with a linear runtime in the same group. How would you describe the runtime of the function below?

TypeScript
function hello3(n: number) {
    console.log("Hello World!");
    console.log("Hello World!");
    for (let i = 0; i < n; i++) {
        console.log("Hello World!");
        console.log("Hello World!");
    }
}

Using the same assumptions as above, it'd be something like $2cn + 2c$, right?

Exactly. Both $2cn + 2c$ and $cn$ are linear functions, identical apart from the principal coefficient and a constant term. The O-notation helps us to ignore these factors focus on the most significant part of the runtime.

And how does that work?

Let's look at the definiiton of the O-notation together.

Let $f, g \colon \mathbb{N} \rightarrow \mathbb{N}$ be two functions defined over the set of natural numbers. We say $f(n) = O(g(n))$, if there are natural numbers $\textcolor{green}{k}, \textcolor{red}{n_0} \in \mathbb{N}$ so that $f(N) \leq \textcolor{green}{k} \cdot g(N)$ for all $N \geq \textcolor{red}{n_0}$.

Don't worry if definitions scare you. Let's break it down.

The central idea of the O-notation is to express that from a certain point on, the function $f(n)$ does not grow faster than another function $g(n)$ apart from a constant factor.

We can say here that $cn = O(2cn+2c)$ by setting e.g. both $\textcolor{green}{k}$ and $\textcolor{red}{n_0}$ to $1$, resulting in $c \cdot N \leq 2c \cdot N + 2c$ for all $N \geq 1$.

Similarly, the expression $2cn+2c = O(cn)$ also holds. Do you see why?

Uhh, Calculus was a long time ago... We can use the inequality $2cn+2c \leq 2cn+2cn = 4cn$ for $n \geq 1$, right? So we can set $\textcolor{green}{k} = 4$ and $\textcolor{red}{n_0} = 1$?

Exactly! And we can do this for all functions with a linear runtime.

In lectures, I've only seen expressions like $O(n)$ or $O(n^2)$, but I never saw something like $O(2cn+2c)$ or $O(cn)$. I didn't even know we could do that.

We could surely notate the class of all linear functions as $O(2cn+2c)$ or even $O(cn)$, but remember that the O-notation makes the constant factor irrelevant? That's why we usually use the simplest form such as $O(n)$.

Ohh, so the O-notation is just a way to classify functions while ignoring the constant factors, I see. But what do we need the $\textcolor{red}{n_0}$ for?

If we get rid of $\textcolor{red}{n_0}$ from the definition, we would need to show that the equality holds for the all natural numbers. Here's a trivial example why that can be a problem.

Since it's clear that $\textcolor{turquoise}{f(n) = (n-1)^2}$ grows much faster than $\textcolor{plum}{g(n)=x+2}$, we should be able to say $g(n) = O(f(n))$. However, there are still points where $\textcolor{turquoise}{f(n)}$ is smaller than $\textcolor{plum}{g(n)}$, e.g. $n=1$! Multiplying by a constant factor doesn't help much here, so we need to provide a starting line from which the inequality holds, so to speak. That's what $\textcolor{red}{n_0}$ is for.

Oh, I've also seen expressions like $f(n) = \Theta(n)$. What does that mean?

If we can use the O-notation bidirectionally, we use the Greek alphabet $\Theta$ instead of $O$.

So saying $f(n) = \Theta(g(n))$ means that both $f(n) = O(g(n))$ and $g(n) = O(f(n))$?

That's correct.

And this doesn't apply in the normal O-notation?

No, it doesn't. The O-notation only tells us: "This function definitely doesn't grow faster than that function", but it doesn't tell us anything about the other way around. You can say that $n = O(n^2)$, but $n^2 = O(n)$ is wrong.

So just to be clear, $n = O(n)$ and $n = O(n^2)$? And this goes for all following $n^k$ with a natural number $k$?

Exactly.

The notation is so confusing! Like, if you write $n = O(n^2)$, is $O(n^2)$ also some kind of function?

It's, uh, complicated. Using the example you brought up, $O(n^2)$ is a set of functions that grow at most as fast as $n^2$. Some argue for using the set membership symbol $f(n) \in O(g(n))$ instead of the equality symbol $f(n) = O(g(n))$ to avoid this confusion. In some cases, $O(n^2)$ is in the meaning of "an arbitrary function that grows at most as fast as $n^2$", used to simplify smaller function terms like $n^3 + 7n^2 + 14n - 12 = n^3 + O(n^2)$.

There's one more thing. You told me earlier that we need a measure independent from time, like, in a physical sense. You never introduced the unit though and went straight to the O-notation. So if I say "My function has a runtime of $O(n)$", I now get that it means something like "With the input length of $n$, my function takes no more than $c \cdot n$ to execute with some constant $c$", but $c \cdot n$ in what, apples? Bananas?

The unit of our choice is steps of a Turing Machine.

What's a Turing Machine?

That's an excellent question! Let's discuss that in the next section.

Something's telling me I shouldn't have asked that question.