Discrete Mathematics Study Center

Growth of Functions

The growth of a function is determined by the highest order term: if you add a bunch of terms, the function grows about as fast as the largest term (for large enough input values).

For example, $f(x) = x^2+1$ grows as fast as $g(x) = x^2 + 2$ and $h(x) = x^2+x+1$ , because for large $x$ , $x^2$ is much bigger than $1$ , $2$ , or $x+1$ .

Similarly, constant multiples don't matter that much: $f(x)=x^2$ grows as fast as $g(x)=2x^2$ and $h(x)=100x^2$ , because for large $x$ , multiplying $x^2$ by a constant does not change it "too much" (at least not as much as increasing $x$ ).

Essentially, we are concerned with the shape of the curve:

Examples of three lines

All three of these functions are lines; their exact slope/y-intercept does not matter.

Only caring about the highest order term (without constant multiples) corresponds to ignoring differences in hardware/operating system/etc. If the CPU is twice as fast, for example, the algorithm still behaves the same way, even if it executes faster.

Big-Oh Notation

Let $f$ and $g$ be functions from $\mathbb{Z} \rightarrow \mathbb{R}$ or $\mathbb{R} \rightarrow \mathbb{R}$ . We say $f(x)$ is $O(g(x))$ if there are constants $c \gt 0$ and $k \gt 0$ such that $0 \le f(n) \le c \times g(n)$ for all $x \ge k$ . The constants $c$ and $k$ are called witnesses. We read $f(x)$ is $O(g(x))$ as " $f(x)$ is big-Oh of $g(x)$ ". We write $f(x) \in O(g(x))$ or $f(x) = O(g(x))$ (though the former is more technically correct).

Basically, $f(x)$ is $O(g(x))$ means that, after a certain value of $x$ , $f$ is always smaller than some constant multiple of $g$ :

Explanation of the definition of big-Oh

Here are some examples that use big-Oh notation:

To show that $5x^2 + 10x + 3$ is $O(x^2)$ : $5x^2 + 10x + 3 \le 5x^2 + 10x^2 + 3x^2 = 18x^2$ Each of the above steps is true for all $x \ge 1$ , so take $c = 18$ , $k=1$ as witnesses.
To show that $5x^2 - 10x + 3$ is $O(x^2)$ : $5x^2 - 10x + 3 \le 5x^2 + 3 \le 5x^2 + 3x^2 = 8x^2$ The first step is true as long as $10x > 0$ (which is the same as $x > 0$ ) and the second step is true as long as $x \ge 1$ , so take $c=8$ , $k=1$ as witnesses.
Is it true that $x^3$ is $O(x^2)$ ?
Suppose it is true. Then $x^3 \le cx^2$ for $x > k$ . Dividing through by $x^2$ , we get that $x \le c$ . This says that " $x$ is always less than a constant", but this is not true: a line with positive slope is not bounded from above by any constant! Therefore, $x^3$ is not $O(x^2)$ .

Typically, we want the function inside the Oh to be as small and simple as possible. Even though it is true, for example, that $5x^2+10x+3$ is $O(x^3)$ , this is not terribly informative. Similarly, $5x^2+10x+3$ is $O(2x^2 + 11x + 3)$ , but this is not particularly useful.

Here are some important big-Oh results:

If $f(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0$ where $a_n \gt 0$ , then $f(x)$ is $O(x^n)$ .
Proof: If $x>1$ , then: $\begin{array}{rcl} f(x) &= & a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0 \\ &\le & |a_n|x^n + |a_{n-1}|x^{n-1} + \cdots + |a_1|x + |a_0| \\ &\le & |a_n|x^n + |a_{n-1}|x^n + \cdots + |a_1|x^n + |a_0|x^n \\ &= & x^n(|a_n| + |a_{n-1}| + \cdots + |a_1| + |a_0|) \end{array}$ Therefore, take $c = |a_n| + |a_{n-1}| + \cdots + |a_1| + |a_0| \gt 0$ and $k = 1$ .
What is the sum of the first $n$ integers? $1+2+3+\cdots+n \le n+n+n+\cdots+n = n \times n = n^2$ Take $c=1,k=1$ to see that sum is $O(n^2)$ . Notice that this agrees with the formula we derived earlier: $\sum_{i=1}^n i = n(n+1)/2$ , which is $O(n^2)$ .
What is the growth of $n!$ ? $\begin{array}{rcl} n! &=& n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 \\ &=& n \times n \times n \times \cdots n \\ &=& n^n \\ \end{array}$ Therefore, $n!$ is $O(n^n)$ with $c=k=1$
What is the growth of $\log n!$ ?
Take the logarithm of both sides of the previous equation to get $\log n! \le \log n^n$ , so $\log n! \le n \log n$ . Therefore, $\log n!$ is $O(n \log n)$ with $c=k=1$ .
How does $\log_2 n$ compare to $n$ ?
We know that $n \lt 2^n$ (we will prove this later). Taking the logarithm of both sides, we have that $\log_2 n \lt \log_2 2^n = n$ . So $\log_2 n$ is $O(n)$ with $c=k=1$ .

When using logarithms inside big-Oh notation, the base does not matter. Recall the change-of-base formula: $\log_b n = \frac{\log n}{\log b}$ . Therefore, as long as the base $b$ is a constant, it differs from $\log n$ by a constant factor.

Here are some common functions, listed from slowest to fastest growth: $O(1), O(\log n), O(n), O(n \log n), O(n^2), O(2^n), O(n!)$ Caution: there are infinitely many functions between each element of this list!

Big-Omega Notation

As we saw above, big-Oh provides an upper bound for a function. To specify a lower bound, we use big-Omega notation.

Let $f$ and $g$ be functions from $\mathbb{Z} \rightarrow \mathbb{R}$ or $\mathbb{R} \rightarrow \mathbb{R}$ . We say $f(x)$ is $\Omega(g(x))$ if there are constants $c \gt 0$ and $k \gt 0$ such that $0 \le c \times g(n) \le f(n)$ for all $x \ge k$ . The constants $c$ and $k$ are called witnesses. We read $f(x)$ is $\Omega(g(x))$ as " $f(x)$ is big-Oh of $g(x)$ ". We write $f(x) \in \Omega(g(x))$ or $f(x) = \Omega(g(x))$ (though the former is more technically correct).

Basically, $f(x)$ is $\Omega(g(x))$ means that, after a certain value of $x$ , $f$ is always bigger than some constant multiple of $g$ :

Explanation of the definition of big-Omega

Here are some examples that use big-Omega notation:

To show that $5x^3 + 3x^2 + 2$ is $\Omega(x^3)$ : $5x^3 + 3x^2 + 2 \ge 5x^3 \ge x^3$ Therefore, take $c=k=1$ .
To show that $x^2 -3x + 4$ is $\Omega(x^2)$ : $\begin{array}{rcl} x^2 - 3x + 4 &=& \frac{1}{2}x^2 + \frac{1}{2}x^2 - 3x + 4 \\ &=& \frac{1}{2}x^2 + \left( \frac{1}{2}x^2 - 3x + 4 \right) \\ &\ge& \frac{1}{2}x^2 \end{array}$ The last step is true as long as $\frac{1}{2}x^2 - 3x + 4 \ge 0$ , which is true when $x \gt 6$ . Therefore, take $c = 1/2, k=6$ .
Is it true that $3x+1$ is $\Omega(x^2)$ ?
Suppose it is true. Then $3x+1 \ge cx^2$ for $x \gt k$ . Dividing through by $x^2$ , we get that $3/x + 1/x^2 \ge c$ . Notice that as $x$ gets bigger, the left hand side gets smaller, so this cannot be true. Therefore, $3x+1$ is not $\Omega(x^2)$ .
What is the sum of the first $n$ integers? $\begin{array}{rcl} && 1+2+3+\cdots+n \\ &\ge& \left\lceil \frac{n}{2} \right\rceil + \left(\left\lceil \frac{n}{2} \right\rceil + 1\right) + \left(\left\lceil \frac{n}{2} \right\rceil + 2\right) + \cdots + n \\ &\ge& \left\lceil \frac{n}{2} \right\rceil + \left\lceil \frac{n}{2} \right\rceil + \cdots + \left\lceil \frac{n}{2} \right\rceil \\ &=& (n-\left\lceil \frac{n}{2} \right\rceil+1)\left\lceil \frac{n}{2} \right\rceil \\ &\ge& \left(\frac{n}{2}\right)\left(\frac{n}{2}\right) \\ &=& \frac{n^2}{4} \end{array}$ Therefore, take $c=1/4,k=1$ to show that the sum is $\Omega(n^2)$ (which matches with our formula for this sum).

Big-Theta Notation

In the previous example, we showed that $\sum_{i=1}^n i = \Omega(n^2)$ . Earlier, we also showed that this sum is $O(n^2)$ . We have special notation for such situations:

Let $f$ and $g$ be functions from $\mathbb{Z} \rightarrow \mathbb{R}$ or $\mathbb{R} \rightarrow \mathbb{R}$ . We say $f(x)$ is $\Theta(g(x))$ if $f(x)$ is $O(g(x))$ and $f(x)$ is $\Omega(g(x))$ . We read $f(x)$ is $\Theta(g(x))$ as " $f(x)$ is big-Theta of $g(x)$ ". We write $f(x) \in \Theta(g(x))$ or $f(x) = \Theta(g(x))$ (though the former is more technically correct).

It might be helpful to think of big-Oh/Omega/Theta as follows:

$\le$ is to numbers as big-Oh is to functions
$\ge$ is to numbers as big-Omega is to functions
$=$ is to numbers as big-Theta is to functions