Introduction to Asymptotic Analysis and Big O
In this lesson, you will learn about asymptotic notation, it is an important tool applied to the analysis of algorithms.
You have seen that the time complexity of an algorithm can be expressed as polynomial. To compare two algorithms, you can compare the respective polynomials. However, the analysis performed in the previous lessons is cumbersome and would become intractable for bigger algorithms that are normally encountered in practice.
Asymptotic analysis
One observation that may help is that you want to worry about large input sizes only. If the input size is really small, how bad can a poorly designed algorithm get, right? Mathematicians have a tool for this sort of analysis called asymptotic notation. The asymptotic notation compares two functions; let’s say, and for large values of . This fits in nicely with your need for comparing algorithms for very large input sizes.
Big O notation
One of the asymptotic notations is the “Big O” notation. A function is considered , which is read as Big Oh of . If a positive real constant and an integer exists, such that the following inequality holds for all :
The following graph shows a plot of a function and that demonstrates this inequality.
Note that the above inequality does not have to hold for all . For , is allowed to exceed but for all values of beyond some value , is not allowed to exceed .
What good is this? It tells you that for large values of , will be within a constant factor of at most. In other words, will not grow faster than a constant multiple of . Put yet another way, the rate of the growth of is within constant factors of that of .
People tend to write = , which isn’t technically accurate. Many functions can satisfy the conditions. Thus, is a set of functions. It is fine to say that belongs to .
Example
Consider an algorithm whose running time is given by . Try to verify that this algorithm’s time complexity is in . To do this, you need to find a positive constant and an integer for all :
The above inequality would still be true if you rewrote it while replacing with . What you have just done is the replacement of the variable part in all terms with , which is the variable-part of the highest order term. This gives us:
This does not violate the inequality because each term on the right-hand side is greater than the corresponding term on the left-hand side. Now, comparing it with the definition of Big-O, you can pick c = 9.
That leaves . For what values of is the inequality satisfied? All of them actually! You can pick .
The above solution is not unique. You could have picked any value for that exceeds the coefficient of the highest power of in . Suppose you decided to pick . The reader can verify that the inequality still holds for or higher.
Note that it is not possible to find a constant and to show that is or . It is possible to show that is or or any higher power of . Mathematically, it is correct to say that is . It gives you a loose bound on the asymptotic running time of the algorithm. When dealing with time and space complexities, you should be generally interested in the tightest possible bound regarding asymptotic notation.
Note: All challenges in this chapter should be answered with the lowest order Big Oh.
Suppose algorithms A and B have a running time of and , respectively. For sufficiently large input sizes, algorithm A will run faster than algorithm B. That does not mean that algorithm A will always run faster than algorithm B.
Both algorithms A and B have running time . The execution time for these algorithms, for very large input sizes, will be within constant factors of each other. For all practical purposes, they are considered equally good.
Simplified asymptotic analysis
Once you have obtained the time complexity of an algorithm by counting the number of primitive operations as discussed in the previous two lessons, you can arrive at the Big O notation for the algorithm by:
- Dropping the multiplicative constants with all terms
- Dropping all but the highest order term
Thus, is , while is .
Notice how the constant coefficients have become insignificant in the Big O notation. Recall that these constants represent the number of primitive operations on a given line of code. This means that while analyzing code, counting a line of code as contributing four primitive operations is as good as counting it as one primitive operation. The only aspect that matters is correctly counting the number of times each line of code is repeated.
Moving forward, you will simplify the analysis by counting the number of executions of each line of code instead of counting the number of operations.
Sometimes the constant coefficients become important. For example, consider algorithms A and B that have a worst-case running time of 100000n + 4 and 10n + 6, respectively. Asymptotically, both are . However, the worst-case running time for algorithm B is numerically better than A.
A comparison of some common functions
It is easy to work with simple polynomials in but when the time complexity involves other types of functions like , you may find it hard to identify the “highest order term.” The following table lists some commonly encountered functions in ascending order of rate of growth. Any function can be given as Big O of any other function that appears in this table.
Function | Name | Function | Name |
---|---|---|---|
Any constant | Constant | Quadratic | |
Logarithmic | Cubic | ||
Log-square | Quartic | ||
Root-n | Exponential | ||
Linear | Exponential | ||
Linearithmic | n-Factorial |
The following graph shows some of the functions from the above table.
A quick quiz on Big O!
is in
True
False