Asymptotic notation

So far, we analyzed linear search and binary search by counting the maximum number of guesses we need to make. But what we really want to know is how long these algorithms take. We're interested in time, not just guesses. The running times of linear search and binary search include the time needed to make and check guesses, but there's more to these algorithms.

The running time of an algorithm depends on how long it takes a computer to run the lines of code of the algorithm—and that depends on the speed of the computer, the programming language, and the compiler that translates the program from the programming language into code that runs directly on the computer, among other factors.

Let's think about the running time of an algorithm more carefully. We can use a combination of two ideas. First, we need to determine how long the algorithm takes, in terms of the size of its input. This idea makes intuitive sense, doesn't it? We've already seen that the maximum number of guesses in linear search and binary search increases as the length of the array increases. Or think about a GPS. If it knew about only the interstate highway system, and not about every little road, it should be able to find routes more quickly, right? So we think about the running time of the algorithm as a function of the size of its input.

The second idea is that we must focus on how fast a function grows with the input size. We call this the rate of growth of the running time. To keep things manageable, we need to simplify the function to distill the most important part and cast aside the less important parts. For example, suppose that an algorithm, running on an input of size $ n $, takes $ 6n^2 + 100n + 300 $ machine instructions. The $ 6n^2 $ term becomes larger than the remaining terms, $ 100 n + 300 $, once $ n $ becomes large enough, 20 in this case. Here's a chart showing values of $ 6n^2 $ and $ 100n + 300 $ for values of $ n $ from 0 to 100:

[[☃ image 2]]

We would say that the running time of this algorithm grows as $ n^2 $, dropping the coefficient 6 and the remaining terms $ 100n + 300 $. It doesn't really matter what coefficients we use; as long as the running time is $ an^2 + bn + c $, for some numbers $ a > 0 $, $ b $, and $ c $, there will always be a value of $ n $ for which $ an^2 $ is greater than $ bn + c $, and this difference increases as $ n $ increases. For example, here's a chart showing values of $ 0.6n^2 $ and $ 1000n + 3000 $ so that we've reduced the coefficient of $ n^2 $ by a factor of 10 and increased the other two constants by a factor of 10:

[[☃ image 2]]

The value of $ n $ at which $ 0.6n^2 $ becomes greater than $ 1000n + 3000 $ has increased, but there will always be such a crossover point, no matter what the constants.

By dropping the less significant terms and the constant coefficients, we can focus on the important part of an algorithm's running time—its rate of growth—without getting mired in details that complicate our understanding. When we drop the constant coefficients and the less significant terms, we use asymptotic notation. We'll see three forms of it: big-$ \Theta $ notation, big-O notation, and big-$ \Omega $ notation.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

Let's look at a simple implementation of linear search:

var doLinearSearch = function(array, targetValue) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  // found it!
    }
  }
  return -1;  // didn't find it
};

Let's denote the size of the array (array.length) by $ n $. The maximum number of times that the for-loop can run is $ n $, and this worst case occurs when the value being searched for is not present in the array.

Each time the for-loop iterates, it has to do several things:

• compare guess with array.length
• compare array[guess] with targetValue
• possibly return the value of guess
• increment guess.

Each of these little computations takes a constant amount of time each time it executes. If the for-loop iterates $ n $ times, then the time for all $ n $ iterations is $ c_1 \cdot n $, where $ c_1 $ is the sum of the times for the computations in one loop iteration. Now, we cannot say here what the value of $ c_1 $ is, because it depends on the speed of the computer, the programming language used, the compiler or interpreter that translates the source program into runnable code, and other factors.

This code has a little bit of extra overhead, for setting up the for-loop (including initializing guess to 0) and possibly returning -1 at the end. Let's call the time for this overhead $ c_2 $, which is also a constant. Therefore, the total time for linear search in the worst case is $ c_1 \cdot n + c_2 $.

As we've argued, the constant factor $ c_1 $ and the low-order term $ c_2 $ don't tell us about the rate of growth of the running time. What's significant is that the worst-case running time of linear search grows like the array size $ n $. The notation we use for this running time is $ \Theta(n) $. That's the Greek letter "theta," and we say "big-Theta of $ n $" or just "Theta of $ n $."

When we say that a particular running time is $ \Theta(n) $, we're saying that once $ n $ gets large enough, the running time is at least $ k_1 \cdot n $ and at most $ k_2 \cdot n $ for some constants $ k_1 $ and $ k_2 $. Here's how to think of $ \Theta(n) $:

[[☃ image 2]]

For small values of $ n $, we don't care how the running time compares with $ k_1 \cdot n $ or $ k_2 \cdot n $. But once $ n $ gets large enough—on or to the right of the dashed line—the running time must be sandwiched between $ k_1 \cdot n $ and $ k_2 \cdot n $. As long as these constants $ k_1 $ and $ k_2 $ exist, we say that the running time is $ \Theta(n) $.

We are not restricted to just $ n $ in big-Θ notation. We can use any function, such as $ n^2 $, $ n \log_2 n $, or any other function of $ n $. Here's how to think of a running time that is $ \Theta(f(n)) $ for some function $ f(n) $:

[[☃ image 2]]

Once $ n $ gets large enough, the running time is between $ k_1 \cdot f(n) $ and $ k_2 \cdot f(n) $.

In practice, we just drop constant factors and low-order terms. Another advantage of using big-Θ notation is that we don't have to worry about which time units we're using. For example, suppose that you calculate that a running time is $ 6n^2 + 100n + 300 $ microseconds. Or maybe it's milliseconds. When you use big-Θ notation, you don't say. You also drop the factor 6 and the low-order terms $ 100n + 300 $, and you just say that the running time is $ \Theta(n^2) $.

When we use big-Θ notation, we're saying that we have an asymptotically tight bound on the running time. "Asymptotically" because it matters for only large values of $ n $. "Tight bound" because we've nailed the running time to within a constant factor above and below.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

When we use asymptotic notation to express the rate of growth of an algorithm's running time in terms of the input size $ n $, it's good to bear a few things in mind.

Let's start with something easy. Suppose that an algorithm took a constant amount of time, regardless of the input size. For example, if you were given an array that is already sorted into increasing order and you had to find the minimum element, it would take constant time, since the minimum element must be at index 0. Since we like to use a function of $ n $ in asymptotic notation, you could say that this algorithm runs in $ \Theta(n^0) $ time. Why? Because $ n^0 = 1 $, and the algorithm's running time is within some constant factor of 1. In practice, we don't write $ \Theta(n^0) $, however; we write $ \Theta(1) $.

Now suppose an algorithm took $ \Theta(\log_{10} n) $ time. You could also say that it took $ \Theta(\log_2 n) $ time. Whenever the base of the logarithm is a constant, it doesn't matter what base we use in asymptotic notation. Why not? Because there's a mathematical formula that says

$ \displaystyle \log_a n = \dfrac{\log_b n}{\log_b a} $

for all positive numbers $ a $, $ b $, and $ n $. Therefore, if $ a $ and $ b $ are constants, then $ \log_a n $ and $ \log_b n $ differ only by a factor of $ \log_b a $, and that's a constant factor which we can ignore in asymptotic notation.

Therefore, we can say that the worst-case running time of binary search is $ \Theta(\log_a n) $ for any positive constant $ a $. Why? The number of guesses is at most $ \log_2 n + 1 $, generating and testing each guess takes constant time, and setting up and returning take constant time. However, as a matter of practice, we often write that binary search takes $ \Theta(\log_2 n) $ time because computer scientists like to think in powers of 2.

There is an order to the functions that we often see when we analyze algorithms using asymptotic notation. If $ a $ and $ b $ are constants and $ a < b $, then a running time of $ \Theta(n^a) $ grows more slowly than a running time of $ \Theta(n^b) $. For example, a running time of $ \Theta(n) $, which is $ \Theta(n^1) $, grows more slowly than a running time of $ \Theta(n^2) $. The exponents don't have to be integers, either. For example, a running time of $ \Theta(n^2) $ grows more slowly than a running time of $ \Theta(n^2 \sqrt{n}) $, which is $ \Theta(n^{2.5}) $.

The following graph compares the growth of $n$,$n^2$, and $n^{2.5}$:
[[☃ image 1]]

Logarithms grow more slowly than polynomials. That is, $ \Theta(\log_2 n) $ grows more slowly than $ \Theta(n^a) $ for any positive constant $ a $. But since the value of $ \log_2 n $ increases as $ n $ increases, $ \Theta(\log_2 n) $ grows faster than $ \Theta(1) $.

The following graph compares the growth of $1$, $n$, and $\log_2 n$:

[[☃ image 1]]

Here's a list of functions in asymptotic notation that we often encounter when analyzing algorithms, ordered by slowest to fastest growing:

1. $ \Theta(1) $
2. $ \Theta(\log_2 n) $
3. $ \Theta(n) $
4. $ \Theta(n \log_2 n) $
5. $ \Theta(n^2) $
6. $ \Theta(n^2 \log_2 n) $
7. $ \Theta(n^3) $
8. $ \Theta(2^n) $
9. $ \Theta(n!) $

Note that an exponential function $a^n$, where $a > 1$, grows faster than any polynomial function $ n^b $, where $ b $ is any constant.

The list above is not exhaustive, there are many functions with running times not listed there. You'll hopefully run into a few of those in your computer science journey.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

We use big-Θ notation to asymptotically bound the growth of a running time to within constant factors above and below. Sometimes we want to bound from only above.

For example, although the worst-case running time of binary search is $ \Theta(\log_2 n) $, it would be incorrect to say that binary search runs in $ \Theta(\log_2 n) $ time in all cases. What if we find the target value upon the first guess? Then it runs in $ \Theta(1) $ time. The running time of binary search is never worse than $ \Theta(\log_2 n) $, but it's sometimes better.

It would be convenient to have a form of asymptotic notation that means "the running time grows at most this much, but it could grow more slowly." We use "big-O" notation for just such occasions.

If a running time is $ O(f(n)) $, then for large enough $ n $, the running time is at most $ k \cdot f(n) $ for some constant $ k $. Here's how to think of a running time that is $ O(f(n)) $:

[[☃ image 1]]

We say that the running time is "big-O of $ f(n) $" or just "O of $ f(n) $." We use big-O notation for asymptotic upper bounds, since it bounds the growth of the running time from above for large enough input sizes.

Now we have a way to characterize the running time of binary search in all cases. We can say that the running time of binary search is always $ O(\log_2 n) $. We can make a stronger statement about the worst-case running time: it's $ \Theta(\log_2 n) $. But for a blanket statement that covers all cases, the strongest statement we can make is that binary search runs in $ O(\log_2 n) $ time.

If you go back to the definition of big-Θ notation, you'll notice that it looks a lot like big-O notation, except that big-Θ notation bounds the running time from both above and below, rather than just from above. If we say that a running time is $ \Theta(f(n)) $ in a particular situation, then it's also $ O(f(n)) $. For example, we can say that because the worst-case running time of binary search is $ \Theta(\log_2 n) $, it's also $ O(\log_2 n) $.

The converse is not necessarily true: as we've seen, we can say that binary search always runs in $ O(\log_2 n) $ time but not that it always runs in $ \Theta(\log_2 n) $ time.

Because big-O notation gives only an asymptotic upper bound, and not an asymptotically tight bound, we can make statements that at first glance seem incorrect, but are technically correct. For example, it is absolutely correct to say that binary search runs in $ O(n) $ time. That's because the running time grows no faster than a constant times $ n $. In fact, it grows slower.

Think of it this way. Suppose you have 10 dollars in your pocket. You go up to your friend and say, "I have an amount of money in my pocket, and I guarantee that it's no more than one million dollars." Your statement is absolutely true, though not terribly precise.

One million dollars is an upper bound on 10 dollars, just as $ O(n) $ is an upper bound on the running time of binary search. Other, imprecise, upper bounds on binary search would be $ O(n^2) $, $ O(n^3) $, and $ O(2^n) $. But none of $ \Theta(n) $, $ \Theta(n^2) $, $ \Theta(n^3) $, and $ \Theta(2^n) $ would be correct to describe the running time of binary search in any case.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

Sometimes, we want to say that an algorithm takes at least a certain amount of time, without providing an upper bound. We use big-Ω notation; that's the Greek letter "omega."

If a running time is $ \Omega(f(n)) $, then for large enough $ n $, the running time is at least $ k \cdot f(n) $ for some constant $ k $. Here's how to think of a running time that is $ \Omega(f(n)) $:

[[☃ image 2]]

We say that the running time is "big-Ω of $ f(n) $." We use big-Ω notation for asymptotic lower bounds, since it bounds the growth of the running time from below for large enough input sizes.

Just as $ \Theta(f(n)) $ automatically implies $ O(f(n)) $, it also automatically implies $ \Omega(f(n)) $. So we can say that the worst-case running time of binary search is $ \Omega(\log_2 n) $.

We can also make correct, but imprecise, statements using big-Ω notation. For example, if you really do have a million dollars in your pocket, you can truthfully say "I have an amount of money in my pocket, and it's at least 10 dollars." That is correct, but certainly not very precise. Similarly, we can correctly but imprecisely say that the worst-case running time of binary search is $ \Omega(1) $, because we know that it takes at least constant time.

Of course, typically, when we are talking about algorithms, we try to describe their running time as precisely as possible. We provide the examples of the imprecise statements here to help you better understand big-$\Omega$, big-$O$, and big-$\Theta$.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.