Big-Oh Notation

The Big-Oh (read it as “big O”) notation lets us describe and compare the work an algorithm does without precisely counting the operations it performs.

Big-Oh has a formal, mathematical definition, but in this course we will work with an informal, intuitive understanding of it.

We use Big-Oh informally in this course

Strictly speaking, Big-Oh is an upper bound: saying something is $O (n)$ means it grows no faster than a constant multiple of $n$ . In this course, when we say an algorithm “is $O (n)$ ,” we will usually mean its tight dominant growth is linear.

Let’s revisit the work of linear search. We said that the work can be expressed as $α n + β$ for some constants $α$ and $β$ . In the Big-Oh notation, we would say that the work of linear search is $O (n)$ . The $O$ stands for “order of”. The $O (n)$ is the canonical way to express a linear relationship between the work and the size of the input.

Let’s try this for another, hypothetical algorithm that does $α n^{2} + β n + γ lo g n + δ$ work. In the Big-Oh notation, we would say that the work of this algorithm is $O (n^{2})$ . The $O (n^{2})$ is the canonical way to express a quadratic relationship between the work and the size of the input.

How do we go from $α n^{2} + β n + γ lo g n + δ$ to $O (n^{2})$ ? It involves two steps.

First, we suppress all coefficients. We set all constants to 1. This gives us $n^{2} + n + lo g n + 1$ .
Second, we ignore (drop) all but the dominant term. This gives us $n^{2}$ .

I will justify both steps in the next two sections. For now, let’s take them as given and use them on an exercise.

Solution

This one is mostly algebra. I will not ask you a question like this on an exam. The point is to see the two steps carried out on a messy expression, not to be quick with the algebra.

I prefer to simplify the expression first, and then apply the two steps:

3 lo g n^{2} + (lo g n)^{2} + (n + 1)^{2} lo g (4 n) = 3 \times 2 lo g n + lo g^{2} n + (n^{2} + 2 n + 1) (lo g 4 + lo g n) = 6 lo g n + lo g^{2} n + (n^{2} + 2 n + 1) (2 + lo g n) = 6 lo g n + lo g^{2} n + 2 n^{2} + 4 n + 2 + n^{2} lo g n + 2 n lo g n + lo g n = n^{2} lo g n + 2 n^{2} + 2 n lo g n + 4 n + lo g^{2} n + 7 lo g n + 2

Now we apply the two steps. Suppressing the coefficients turns the expression into $n^{2} lo g n + n^{2} + n lo g n + n + lo g^{2} n + lo g n + 1$ . Dropping all but the dominant term leaves $n^{2} lo g n$ . So the work is $O (n^{2} lo g n)$ .

You might be wondering how I decided that $n^{2} lo g n$ is the dominant term. To compare two terms, divide one by the other and ask what happens as $n$ grows. Take $n^{2} lo g n$ and $2 n^{2}$ . Divide the first by the second and you get $\frac{l o g n}{2}$ , which keeps growing as $n$ grows. So the first term grows faster than the second. Divide $n^{2} lo g n$ by $2 n lo g n$ and you get $\frac{n}{2}$ , which also keeps growing. The remaining terms $4 n$ , $lo g^{2} n$ , $7 lo g n$ , and $2$ grow more slowly than $2 n lo g n$ . So $n^{2} lo g n$ is the dominant term.

I assumed $lo g n$ means $lo g_{2} n$ here. That is the usual convention in computer science.