Asymptotic Notation

Asymptotic notation are formal notational methods for stating the upper and lower bounds of a function. The notations used when describing resource needs. These are: $O(f(n)), o(f(n)), \Omega(f(n))$, and $\Theta(f(n))$ (Pronounced, Big-O, Little-O, Omega and Theta respectively). The f(n) inside each of these notations is a description of a curve like we saw in the previous section. They describe the shape of a line.

Formally

" $T(n)$ is $O(f(n))$" iff for some constants $c$ and $n_0$, $T(n) \leq c f(n)$ for all $n \geq n_0​​$

" $T(n)$ is $\Omega(f(n))$" iff for some constants $c$ and $n_0$, $T(n) \geq c f(n)$ for all $n \geq n_0​​$

" $T(n)$ is $\Theta(f(n))$" iff $T(n)$ is $O(f(n))$ and $T(n)$ is $\Omega(f(n))$

" $T(n)$ is $o(f(n))$" iff $T(n)$ is $O(f(n))$ and $T(n)$ is NOT $\Theta(f(n))$

iff is the mathematical shorthand for "if and only if"

Informally

" $T(n)$ is $O(f(n))$" basically means that the function $f(n)$ describes the upper bound for $T(n)$

" $T(n)$ is $\Omega(f(n))$" basically means that the function $f(n)$ describes the lower bound for $T(n)$

" $T(n)$ is $\Theta(f(n))$" basically means that the function $f(n)$ describes the exact bound for $T(n)$

" $T(n)$ is $o(f(n))$" basically means that the function $f(n)$ describes the upper bound for $T(n)$ where $T(n)$ will never actually be reached

Worst case, Best Case, Average Case

The asymptotic notation system for bounds is often confused with the idea of worst case, best case and average case. They are actually very different things. Big-O does not describe a worst case, Omega does not describe a best case. Big-O describes an upper bound on each of these cases. Similarly Omega describes a lower bound on each of these cases. We should not mix up this idea.

In practice, most of the time we deal with either worst case or average case. We rarely ever consider best case. Each case can still have an upper bound(big-O) or lower bound (Omega).

An easy way to think about Asymptotic Notation

The math in algorithms analysis can often be intimidates students. One of the simplest ways to think about algorithms analysis is that it is basically a way to apply a rating system for your algorithms (like movie ratings). It tells you the kind of resource needs you can expect the algorithm to exhibit as your data gets bigger and bigger. From lowest resource growth to highest resource growth, the rankings are: $O(1)$ , $O(\log n)$ , $O(n)$ , $O(n log ⁡n)$ , $O(n^2)$ , $O(n^3)$ , $O(2^n)$ . Think about the graphs in the grow rate section. The way each curve looks. That is the most important thing to understand about algorithms analysis.

A closer look at the definition of big-O

Mathematical definitions are typically exact. If you say that a < b then a is always smaller than b... there isn't any room for anything else. What the notations used in algorithms analysis do is relax this exactness. It allows us to get an idea of resource usage without having to be completely exact about it.

Let's take a closer look a the formal definition for big-O analysis

" $T(n)$ is $O(f(n))$" iff for some constants $c$ and $n_0$, $T(n) \leq c f(n)$ for all $n \geq n_0​​$

Start with the first portion of the statement

" $T(n)$ is $O(f(n))$ iff"

The above is portion is stating what we are defining. In other words, that part says: In order for $T(n)$ to be $O(f(n))$ it must meet the criteria set out in the rest of the definition. It also gives you an idea of what pieces are involved with the definition

• n is the size of the data set.

• T(n) is a function that describes the usage of a resource with respect to n

• f(n) is a function that describes a curve.

• O(f(n)) means that the curve described by f(n) is an upper bound for the resource needs of a function T(n)

The next part of the definition:

... for some constants $c$ and $n_0$,...

$c$ and $n_0$ refer to two values that are both constants. constants are values that do not change with respect to n. That is no matter what n is $c$ and $n_0$ must stay the same. The exact value of $c$ and $n_0$ are not defined, but in order for the definition to be true, we must be able to find a value for each of these constants such that the rest of the statement is true.

...$T(n) \leq c f(n)$...

This means that if we were to plot $T(n)$ on a graph, the $T(n)$ curve would fall underneath some stretched (scaled by a constant) version of the $f(n)$ curve. What this means is that $T(n)$ does not have to be under the specific curve described by $f(n)$. It is allowed to fall under a constantly scaled version of the $f(n)$. For example instead of having to be under an exact curve like $n^2$ , it can be under the $10 n^2$ curve or even the $200 n^2$ curve. In fact it can be any constant, as long as it is a constant. A constant is simply a number that does not change with $n$ . So as $n$ gets bigger, you cannot change what the value for $c$ . The actual value of the constant does not matter though.

The last portion of the definition is:

... for all $n\geq n_0$

This is another relaxation of the mathematical definition. It means part of the $T(n)$ curve is allowed to actually be above the $cf(n)$ curve. $T(n)$ simply fall under the $cf(n)$ curve at some value of $n$ (we call this point $n_0$ ). and once it falls under the $cf(n)$ curve, it cannot go back above the curve for any value of n greater than $n_0$

In summary, when we are looking at big-O, we are in essence looking for a description of the growth rate of the resource increase. The exact numbers do not actually matter in the end.