Asymptotic Growth (Big O and More)

There are several notions that are utilized in complexity theory to express the growth rate of functions and it gives us a mathematical framework to compare the speed at which functions grow. Our focus will be on counting functions \phi(n): \mathbb{N} \rightarrow \mathbb{N}, however, we can use utilize tools and intuition from analysis (calculus) to understand their growth rates.

Motivation: Let f(x)=x^2+300, g(x)=2x^2+1 and h(x)=x^3 (we will really only consider on the domain (0,\infty)). Suppose we wanted to understand which function grows faster as the input increases. We cannot simply say that g(x)\leq h(x), even though intuitively cubic polynomials should be larger than quadratic polynomials. In particular,

    \[3=g(1)> h(1)=1 \text{ and } 9=g(2)>h(2)=8 \text{ and } 19=g(3)<h(3)=27\]

and for all integers n \geq 3, we have that g(n)\leq h(n). Therefore, we can quickly conclude that simply comparing the functions will not give us the flexibility we’d like. Therefore, we need an approach which focuses on long-term behavior.

Definition Let f,g: \mathbb{N} \rightarrow \mathbb{N}. We say g(n)=O(f(n)) if g asymptotically grows at most the same rate as f, i.e. \vert g(n) \vert \leq c\cdot f(n) for some c>0 and sufficiently large n \in \mathbb{N}. This is known as big-O notation.

Example: Let f(n)=n^2+300 and g(n)=2n^2+1, then \vert 2n^2+1 \vert \leq 2\cdot (n^2+300) = 2n^2+600 when n\geq 1. Therefore, g(n)=O(n^2+300).

Of course, we could any c\geq 2; however, it does not matter in showing g(n)=O(n^2+300). It is more common to consider a more basic function such as n^2. In the next example, we will see multiple choices for c,

Example: Let f(n)=n^2 and g(n)=2n^2+1. Note c=2 no longer works here. Since 2n^2+1\geq 2n^2 for all n \in \mathbb{N}.

    \begin{align*} \vert 2n^2+1 \vert \leq 3\cdot n^2 && \text{ for } n\geq 1 \\ \vert 2n^2+1 \vert \leq 2.1\cdot n^2 && \text{ for } n\geq 4 \\ \vert 2n^2+1 \vert \leq 2.01\cdot n^2 && \text{ for } n\geq 10 \\ \vert 2n^2+1 \vert \leq 2.001\cdot n^2 && \text{ for } n\geq 32 \\ \end{align*}

Therefore, g(n) = O(n^2).

In this case, we can choose c>2. The reason is, we must overcome the constant term 1, so c=2 is not enough.

Exercise: Show that n^2 + \lceil \sqrt{n} \rceil = O(n^2). Hint: Consider a function such that \lceil \sqrt{n} \rceil \leq f(n) \leq n^2.

For any c \in \mathbb{R} and functions f and g,

  1. c\cdot f(n) = O(f(n))
  2. O(f(n))+O(g(n)) = O(f(n)+g(n))
  3. O(f(n))\cdot O(g(n)) = O(f(n)\cdot g(n))
In other words, multiplying a function by a constant does not affect how it grows asymptotically, and we can determine the big-O of a sum and product by looking at the individual terms and factors. The last property one should observe can be described in the following example:

Example: Let g(n)=2n^2+1 and h(n)=n^3. Note that earlier, we had 19=g(3). Therefore,

    \[\vert 2n^2+1\vert \leq 1\cdot n^3\]


for n\geq 1. Therefore, g(n)=O(n^3).

Therefore, we have seen that g(n)=O(n^2) and g(n)=O(n^3). This is because g(n) grows asymptotically at most the same rate as both n^2 and n^3. This can cause some confusion because of the usage of “=.” This is simply because n^3 grows faster than n^2 and thus every function which is O(n^2) is necessarily O(n^3) as well (if you grow at most as fast as n^2, then clearly you should grow at most as fast as n^3). There are variations of the big-O, we list them all (including big-O for reference):

Let f,g: \mathbb{N} \rightarrow \mathbb{N},

  1. g(n)=O(f(n)) if g asymptotically grows at most the same rate as f, i.e. \vert g(n)\vert\leq cf(n) for some c>0 and n sufficiently large. This is big O.
  2. g(n)=\Omega(f(n)) if g asymptotically grows at least the same rate as f, i.e. \vert g(n)\vert\geq cf(n) for some c>0 and n sufficiently large. This is big Omega.
  3. g(n)=\Theta(f(n)) if g asymptotically grows the same rate as f, i.e. g(n)=O(f(n) and g(n)=\Omega(f(n)). This is big Theta.
  4. g(n)=o(f(n)) if g asymptotically grows slower than f, i.e. \lim\limits_{n \to \infty} \frac{g(n)}{f(n)}=0. This is little o.
  5. g(n)=\omega(f(n)) if g asymptotically grows faster than f, i.e. \lim\limits_{n \to \infty} \frac{f(n)}{g(n)}=0. This is little omega.