1  Big-O Notation

This section recalls big-O notation. Throughout the course, we will use big-O to analyze algorithms in terms of time and space complexity.

Objectives. After learning this material, you should be able to:

• Recall the formal definition of big-O notation, \(f = O(g)\).
• Prove that \(f = O(g)\) using a \(C,N\) proof.
• Prove that \(f = O(g)\) using a limit proof.
• Recall the definitions of big-Omega \(\Omega(g)\), big-Theta \(\Theta(g)\), little-o \(o(g)\), and little-omega \(\omega(g)\).
• Sort functions by asymptotic growth rate, from least to highest.
• Given two functions \(f,g\), state which of the following are true or false: \(f = O(g)\), \(f = \Omega(g)\), \(f = \Theta(g)\), \(f = o(g)\), \(f = \omega(g)\).

1.1 Motivation and Intuition

We often want to compare algorithms to see which is faster or uses less memory. But that depends on details: the hardware they’re running on, the particular inputs, and more. So we’ll step back and get a rough sense of an algorithm’s performance by bounding its asymptotic performance as the inputs get larger and larger. We will discuss this in detail next chapter, but for now, just know that big-O will be our tool to get rough estimates that don’t depend on details such as hardware performance.

Important: big-O applies to any functions, not just runtime or space usage. We will consider the big-O properties of any function \(f: \mathbb{R} \to \mathbb{R}\), although we will often have that \(f(n)\) is the runtime of an algorithm on inputs of size \(n\) (discussed soon).

With big-O, we will focus on the “asymptotic growth rate” of functions as we zoom out and the functions grow toward infinity.

So far, \(n^2\) is the largest function, but let’s zoom out.

The picture changes as we continue to the right.

In fact, even if we multiply \(n^2\) by a large constant, like 1000, by zooming out, it becomes clear that \(2^n\) grows faster. This can also be illustrated with a chart.

\(n\)	\(f(n)=n^2\)	\(h(n) = 1000n^2\)	\(g(n) = 2^n\)
1	1	1,000	2
10	100	100,000	~1,000
20	400	400,000	~1,000,000
30	900	900,000	~1,000,000,000
40	1,600	1,600,000	~1,000,000,000,000
50	2,500	2,500,000	~1,000,000,000,000,000

Here, \(h(n) = 1000n^2\) begins much larger than \(g(n) = 2^n\), but as \(n\) increases, the latter quickly becomes much, much larger. We will see that this behavior still occurs if the 1000 in \(h(n) = 1000n^2\) is replaced with any constant, however large. On the other hand, in a sense, \(f(n) = n^2\) and \(h(n) = 1000n^2\) grow at the same rate: the gap between them remains the same, multiplicatively speaking. We will formalize this idea with big-O.

1.2 Formalizing Big-O

Let \(f: \mathbb{R} \to \mathbb{R}\) and \(g: \mathbb{R} \to \mathbb{R}\). Recall this means that \(f\) and \(g\) are functions that take in real numbers and output real numbers. Also assume that \(f(n) > 0\) and \(g(n) > 0\) for all \(n\), which will be the case for space and runtime and will make our lives simpler.

Definition 1.1 (Big-O) Say that \(f = O(g)\) if there exist positive numbers \(C,N\) such that, for all \(n \geq N\), \(f(n) \leq C \cdot g(n)\).

In this definition, \(N\) is a lower cutoff. We only consider the behavior of \(f\) and \(g\) for “large” inputs, i.e. \(n \geq N\). To understand the constant factor \(C\), consider the next example.

Example 1.1 Let \(f(n) = 5n^2\) and \(g(n) = n^2\). Here \(f\) is larger than \(g\), but only by a constant factor. They grow at the same rate: \(f = O(g)\). We can prove this by showing that the definition of big-O holds with \(N=1\) and \(C=5\).

Proof: for all \(n \geq 1\), we have \(f(n) \leq 5g(n)\), as required.

Example 1.2 Let \(f(n) = n^2\) and \(g(n) = n^3\). We will prove that \(f = O(g)\) with constants \(C=1,N=1\). To satisfy the definition, we have to prove that, for all \(n \geq 1\), we have \(n^2 \leq n^3\).

Proof: We have \(n^2 = 1 \cdot n^2 \leq n \cdot n^2 = n^3\), completing the proof.

To understand these proofs, you can plot \(f(n)\), \(g(n)\), and \(C\cdot g(n)\). Visualizing can also be helpful on the examples below.

Example 1.3 Let \(f(n) = 10n^2\) and \(g(n) = n^3\). We will prove that \(f = O(g)\) with constants \(C=10,N=1\). We have to prove that, for all \(n \geq N\), we have \(10n^2 \leq C n^3\). In this case, we must prove for all \(n \geq 1\) that \(10n^2 \leq 10n^3\).

Proof: If \(n \geq 1\), then \(10n^2 \leq 10n^2 \cdot n\), so \(10n^2 \leq 10n^3\).

Example 1.4 We can give an alternate proof of the previous example using different constants. Let us pick \(C = 1, N=10\). If \(n \geq N\), then \(n \geq 10\), so \(10n^2 \leq n \cdot n^2 = n^3 = C n^3\). We have proven that \(10n^2 \leq 1 \cdot n^3\) for all \(n \geq 10\).

As the examples show, there is generally not just one correct choice of \(N\) and \(C\) that works to prove \(f = O(g)\). You can now try on the next example. Remember that you get to pick whichever \(N\) and \(C\) you want to make the proof work.

Exercise 1.1 Let \(f(n) = 20n^2\) and \(g(n) = 5n^3\). Prove that \(f = O(g)\).

Note on writing functions. We will often refer to an expression such as \(1000n^2\) as being a function, namely the function that maps \(n\) to \(1000n^2\). If \(f(n) = 4n\) and \(g(n) = 1000n^2\), all of these are valid ways of writing the same thing:

• \(f(n) = O(g(n))\)
• \(f = O(g)\)
• \(f = O(1000n^2)\)
• \(4n = O(g)\)
• \(4n = O(1000n^2)\)

1.3 Big-O proofs

To come up with a big-O proof, you often need to do some scratch work and calculation to find \(N\) and \(C\). You should first do all the scratch work to figure them out, then write a fresh clean proof using the numbers you have found.

Example 1.5 (Scratch work) Suppose we are asked to prove that \(5n^2 + 3 = O(n^2)\). We can first use a common approach for big-O, which is to upper-bound low-order terms by a higher order. In this case, \(3 \leq 3n^2\), so \(5n^2 + 3 \leq 5n^2 + 3n^2 = 8n^2\). However, here we need to be careful and notice that our inequality \(3 \leq 3n^2\) only holds for \(n \geq 1\). So to use it, we will need to choose \(N\) at least \(1\). Now, we note that we can choose \(C = 8\) and we will be done, because \(8n^2 = Cn^2\). We have found that \(N=1,C=8\) will work for our proof.

Warning: the above scratch work is not a proof! Now that we’ve done the scratch work, we need to turn it into a good proof.

Example 1.6 (Finished proof) We choose \(C=8,N=1\). For all \(n \geq 1\), we have \(3 \leq 3n^2\). So in this case, \[\begin{align} 5n^2 + 3 &\leq 5n^2 + 3n^2 \\ &= 8n^2 \\ &= Cn^2. \end{align}\] \[ \tag{1.1}\] This proves \(5n^2 + 3 = O(n^2)\).

We call this a “\(C,N\)” proof that \(f = O(g)\). Next we’ll see a different type of proof, a “limit” proof.

Remark 1.1. In Equation 1.1, we had an array of equalities and inequalities. Such an array should be read as follows: \[\begin{align} \textrm{$5n^2 + 3$ is less than or equal to $5n^2 + 3n^2$} \\ \textrm{which is equal to $8n^2$} \\ \textrm{which is equal to $Cn^2$ .} \end{align}\] We showed that the first expression is less than or equal to something that is equal to something that is equal to the final expression. This allows us to conclude that the first expression, \(5n^2+3\), is less than or equal to the last expression.

1.4 Calculus proofs

Often, the easiest way to prove a big-O statement is to use the following fact.

Proposition 1.1 If \(\lim_{n \to \infty} \frac{f(n)}{g(n)} \leq D\) for some real number \(D\), then \(f = O(g)\).

Example 1.7 Let’s show that, for \(f(n) = 8n^4\) and \(g(n) = n^4\), we have \(f = O(g)\). We have \(\frac{f(n)}{g(n)} = \frac{8n^4}{n^4} = 8\). So \(\lim_{n \to \infty} \frac{f(n)}{g(n)} = 8\), so \(f = O(g)\).

Using Proposition 1.1 in this way is called a “limit proof” of big-O. Limit proofs often use the following:

Proposition 1.2 (L’Hopital’s Rule) If \(f(n) \to \infty\) and \(g(n) \to \infty\) as \(n \to \infty\), then \(\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{f'(n)}{g'(n)}\), where \(f'\) and \(g'\) are the derivatives, assuming the limit exists.

Example 1.8 Let’s use a limit proof to show that, for \(f(n) = 3n^2 + 2\) and \(g(n) = n^3\), we have \(f = O(g)\). We consider \(\lim_{n \to \infty} \frac{f(n)}{g(n)}\). Both the numerator and denominator approach infinity as \(n\) grows. We have \(f'(n) = 6n\) and \(g'(n) = 3n^2\). So by L’Hopital’s rule, \(\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{f'(n)}{g'(n)} = \frac{6n}{3n^2} = \frac{2}{n}\). Since \(\lim_{n \to \infty} \frac{2}{n} = 0\), we conclude that \(\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0\), which is a constant.

Example 1.9 Let’s use a limit proof to prove that \(n^2 = O(e^n)\). Both functions approach infinity. We remember that \(\tfrac{d}{dn} n^2 = 2n\) and \(\tfrac{d}{dn} e^n = e^n\). So by L’Hopital’s rule, \(\lim_{n \to \infty} \frac{n^2}{e^n} = \lim_{n \to \infty} \frac{2n}{e^n}\). Now we use L’Hopital’s rule again to get \(\lim_{n \to \infty} \frac{2}{e^n} = 0\). Since the limit is zero, we have \(n^2 = O(e^n)\).

It’s useful to remember that \(2^n = e^{a \cdot n}\) for a positive constant \(a\). Therefore, using the chain rule, \(\tfrac{d}{dn} 2^n = \tfrac{d}{dn} e^{a \cdot n} = a e^{a \cdot n} = a 2^n\). In other words, the derivative of \(2^n\) behaves almost like the derivative of \(e^n\), except that a positive constant comes out front.

Similarly, we recall that \(\frac{d}{dn} \ln(n) = \frac{1}{n}\), and \(\log_2(n) = b \ln(n)\) for some positive constant \(b\). This means that \(\log_2(n) = O(\ln(n))\) and vice versa.

Let’s use a limit proof to prove that \(\log_2(n) = O(2^n)\). Both functions approach infinity as \(n \to \infty\), so we can use L’Hopital’s rule. \(\lim_{n \to \infty} \tfrac{\log_2(n)}{2^n} = \lim_{n \to \infty}\frac{c (1/n)}{2^n}\) for some constant \(c > 0\). Continuing, we get \(\lim_{n \to \infty} \frac{c}{n 2^n} = 0\), because the numerator is a constant and the denominator approaches infinity. Since the limit is zero, \(\log_2(n) = O(2^n)\).

1.5 Comparing growth rates

Here are some of the most common types of functions you will encounter.

• Constant functions: \(f(n) = a\) for some real number \(a\). All constant functions can be described as \(O(1)\).
• Linear functions: \(f(n) = a \cdot n\) for some positive constant \(a\), such as \(f(n) = 4n\). We can abuse terminology and use “linear” to refer to functions of the form \(a \cdot n + b\) for some positive constant \(a\) and some constant \(b\), such as \(f(n) = 4n + 2\).
• Quadratic functions: \(f(n) = a \cdot n^2\) for some positive \(a\).
• Polynomial functions: these are functions of the form \(f(n) = a_k n^k + a_{k-1} n^{k-1} + \cdots + a_1 n + a_0\) for some constants \(a_0,\dots,a_k\). Examples include \(f(n) = 8n^3 - 2n^2 + 4n + 1\) and \(f(n) = 5n^{100} + 2n^{33}\). Linear and quadratic functions are examples of polynomials, as are constant functions. In this context, we usually assume \(a_k\) is positive so that \(f(n) \to \infty\) as \(n \to \infty\). We say that the degree of the polynomial is \(k\), where \(k\) is the highest power.
• More generally, if \(f(n) = n^a\) for some positive constant \(a\), even if \(a\) is not an integer, we abuse terminology and say that \(f\) has a polynomial growth rate.
• Logarithmic functions: these are functions of the form \(f(n) = \log_2(n)\), or more generally \(f(n) = a \cdot \log_2(n)\) for some positive constant \(a\). Remember your rules of logarithms! \(a \log_2(n) = \log_2(n^a)\).
• Polylogarithmic functions: these are less common, but they are functions of the form \(\left(\log_2(n)\right)^k\) for some positive constant \(k\), e.g. \((\log_2(n))^2\). Logarithmic functions are polylogarithmic, corresponding to the case \(k=1\).
• Exponential functions: these are functions of the form \(2^{a \cdot n}\) for positive constant \(a > 0\). Sometimes, other functions with \(n\) in the exponent, such as \(2^{n^2}\), are also referred to as being exponential in \(n\).

We always have the following rules of comparison with regard to big-O:

constant \(\ll\) polylogarithmic \(\ll\) polynomial \(\ll\) exponential

where \(\ll\) is shorthand for “is big-O of”. Furthermore, we can say the following:

If \(f(n)\) is a polynomial of degree \(k\), then \(f = O(n^k)\).

And:

If \(k' \geq k\), then \(n^k = O(n^{k'})\).

Another useful rule of thumb is that if \(a,b > 1\), then \(\log_a(n) = O(\log_b(n))\) and vice versa, where \(a\) and \(b\) are the bases of the logarithms. Because of this, we can be a bit informal and not always specify the bases of our logarithms. In this class, \(\log(n)\) will generally mean log base \(2\) and \(\ln(n)\) will always mean log base \(e\). All of these facts can be proven using the \(C,N\) definition of big-O (or using calculus, for example).

Exercise 1.2 Suppose we are asked to compare \(f(n) = 10 \log(n)\) and \(g(n) = 10^n\). Do we have \(f = O(g)\), \(g = O(f)\), both, or neither?

Solution.

We have \(f = O(g)\), but not the other way around. Logarithmic functions grow much slower than exponential functions.

Exercise 1.3 Compare \(f(n) = 8n^3 + 2n^2\), \(g(n) = 0.1 n^4\), and \(h(n) = (\log(n))^{300}\). Order them by asymptotic growth rate from slowest to fastest (smallest to largest).

Solution.

\(h, f, g\). Any polylogarithmic (that is \(\log(n)\) raised to a power) grows slower than any polynomial (that is, \(n\) raised to a power). So \(h\) is the slowest growing. \(f\) grows asymptotically at the speed of \(n^3\), which is slower than the \(n^4\) of \(g\).

Other functions. There are many functions that do not fall directly into the categories listed above. A common example in computer science is the function \(f(n) = n \log(n)\). Comparing the growth rate of such functions may take some work.

Example 1.10 We prove that \(n \log(n) = O(n^2)\) using a \(C,N\) proof.

In this class, you may take as given the fact that \(\log(n) \leq n\) for all \(n \geq 0\), when the log is base \(2\) or \(e\). This can be proved directly with calculus.

Using this fact, \(n \log(n) \leq n \cdot n = n^2\) for all \(n \geq 0\). We conclude that, with \(N=0\) and \(C=1\), the definition of big-O is satisfied.

1.6 Other Asymptotic Notation

There are several other pieces of asymptotic notation to remember. We will often use these pieces of notation, although big-O is the most common.

Definition 1.2 (Big Omega) We say \(f = \Omega(g)\) if \(g = O(f)\).

Here, \(\Omega\) is the Greek letter capital Omega. Big Omega says that \(f\) grows asymptotically at least as fast as \(g\). For example, \(2^n = \Omega(n)\).

Definition 1.3 (Big Theta) We say \(f = \Theta(g)\) if \(f = O(g)\) and \(g = O(f)\).

Here, \(\Theta\) is the Greek letter capital Theta. Big Theta says that \(f\) and \(g\) grow asymptotically at the same rate. For example, any two polynomials of the same degree are big-Theta of each other. E.g., take \(f(n) = 3n^2 + 200\) and \(g(n) = 45n^2 - 30\), then \(f = \Theta(g)\). We can prove this by first proving \(f = O(g)\), then proving \(g = O(f)\).

Definition 1.4 (Little o) We say \(f = o(g)\) if \(\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0\).

In other words, \(f\) does not grow as fast as \(g\). For example, \(n = o(n^2)\). In fact, if \(k' > k\), the \(n^k = o(n^{k'})\). This follows directly from the definition of little \(o\).

Definition 1.5 (Little omega) We say \(f = \omega(g)\) if \(g = o(f)\).

Here, \(\omega\) is the Greek letter lowercase omega. Little omega says that \(f\) grows “strictly” faster than \(g\). Little-omega mirrors little-o in the same way that big-Omega mirrors big-O.

Here is a quick guide, but remember that this comparison to inequality operators is only an analogy.

Symbol	similar to	Meaning (up to a constant factor)
\(O(n)\)	\(\leq\)	asymptotically at most
\(o(n)\)	\(<\)	asymptotically less; shrinking compared to
\(\Omega(n)\)	\(\geq\)	asymptotically at least
\(\omega(n)\)	\(>\)	asymptotically more; diverging compared to
\(\Theta(n)\)	\(=\)	asymptotically the same

Based on our previous discussions, we know the following general facts.

• If \(f\) is polylogarithmic and \(g\) is polynomial, then \(f = o(g)\).
• If \(f\) is exponential and \(g\) is polynomial, then \(f = \omega(g)\).
• If \(f\) is bounded by a constant and \(g(n) \to \infty\), then \(f = o(g)\).

You should now be able to answer the following questions.

• Let \(f(n) = 2n^2\) and \(g(n) = \log(n)\). Which of the following are true and which are false? \(f = O(g)\), \(f = \Omega(g)\), \(f = \Theta(g)\), \(f = o(g)\), \(f = \omega(g)\).
• Let \(f(n) = 8^n\) and \(g(n) = n\log(n)\). Which of the following are true and which are false? \(f = O(g)\), \(f = \Omega(g)\), \(f = \Theta(g)\), \(f = o(g)\), \(f = \omega(g)\).

One very useful fact is that if \(f = O(g)\) and \(h = O(g)\) also, then \(f + h = O(g)\). We can interpret this as a fact about running times of algorithms: if we have two algorithms with running times \(f\) and \(h\) respectively, and both of them are \(O(g)\), the running first one algorithm and then the other will give an asymptotic running time of \(f+h = O(g)\) as well.