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)),Ω(f(n))O(f(n)), o(f(n)), \Omega(f(n)), and Θ(f(n))\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)T(n) is O(f(n))O(f(n))" iff for some constants cc and n0n_0, T(n)cf(n)T(n) \leq c f(n) for all nn0​​n \geq n_0​​

" T(n)T(n) is Ω(f(n))\Omega(f(n))" iff for some constants cc and n0n_0, T(n)cf(n)T(n) \geq c f(n) for all nn0​​n \geq n_0​​

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

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

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

Informally

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

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

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

" T(n)T(n) is o(f(n))o(f(n))" basically means that the function f(n)f(n) describes the upper bound for T(n)T(n) where T(n)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(1) , O(logn)O(\log n) , O(n)O(n) , O(nlogn)O(n log ⁡n) , O(n2)O(n^2) , O(n3)O(n^3) , O(2n)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)T(n) is O(f(n))O(f(n))" iff for some constants cc and n0n_0, T(n)cf(n)T(n) \leq c f(n) for all nn0​​n \geq n_0​​

Start with the first portion of the statement

" T(n)T(n) is O(f(n))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)T(n) to be O(f(n))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 cc and n0n_0,...

cc and n0n_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 cc and n0n_0 must stay the same. The exact value of cc and n0n_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)cf(n)T(n) \leq c f(n)...

This means that if we were to plot T(n)T(n) on a graph, the T(n)T(n) curve would fall underneath some stretched (scaled by a constant) version of the f(n)f(n) curve. What this means is that T(n)T(n) does not have to be under the specific curve described by f(n)f(n). It is allowed to fall under a constantly scaled version of the f(n)f(n). For example instead of having to be under an exact curve like n2n^2 , it can be under the 10n210 n^2 curve or even the 200n2200 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 nn . So as nn gets bigger, you cannot change what the value for cc . The actual value of the constant does not matter though.

The last portion of the definition is:

... for all nn0n\geq n_0

This is another relaxation of the mathematical definition. It means part of the T(n)T(n) curve is allowed to actually be above the cf(n)cf(n) curve. T(n)T(n) simply fall under the cf(n)cf(n) curve at some value of nn (we call this point n0n_0 ). and once it falls under the cf(n)cf(n) curve, it cannot go back above the curve for any value of n greater than n0n_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.

Last updated