There’s a mathematical way to measure the efficiency of an algorithm in terms of the time and space required to execute it. It’s called asymptotic analysis.
The performance of most algorithms changes as the sizes of their inputs change. Asymptotic analysis gives us a way to describe that change in performance with a mathematical notation that can be turned into a visual graph.
Asymptotic or complexity analysis is the evaluation of how much time and space an algorithm will use and how the use of those resources will grow with respect to input size, independent of the hardware and software implementations.
Ways of analyzing Algorithms
There are three ways to analyze algorithms with respect to input size:
- Best Case: When the algorithm has the best performance it can
- Average Case: How the algorithm performs on average
- Worst Case: When the algorithm has the worst performance it can
Let’s understand these cases with an example. Given the following list/array:
Suppose we need to perform a linear search on that list for a certain number v.
The best case would be if v was 10, because it would be found in the first search. If the size of the array increased, it would still require only one search iteration. This is the best-case analysis.
The worst case would be if v was not in the list. In this case, the entire list would have to be traversed just to find out that v is not in the list. That’d require 7 steps to complete. This is the worst-case analysis.
The average case is a little bit different. The element we’re looking for can be anywhere between the first and last positions in the array. Given that n is the length of the list, we will do at least one comparison and at most n comparisons. When we reach the element at position k, we have done k comparisons.
In order to average those comparisons, you sum the total number of possible comparisons, 1 + 2 + 3 … + n, which can be calculated by the formula ((n + 1) · n) / 2, and divide the result by n, and so we would have:
So it takes around half the length of the list to search for an element using linear search. In our case, it would be (7 + 1) / 2 = 4 steps on average.
Keep in mind that the average case analysis presented here is simple and it is not easy to do in most practical cases and it is rarely done. It is not easy to do because you have to take all possible inputs into account and calculate all their computing times, then sum those values and divide the result by the total number of inputs. It’s some really complex math to get the correct result for the average case in most analyses.
Which analysis is generally used?
We do worst-case analyses to assess algorithms most of the time because knowing how the algorithm will perform at its worst is great information.
We rarely do average-case analysis because, as I said, they’re hard to do.
Best-case analyses are useless because an algorithm may perform well with certain inputs but may take years to run in the worst case.
Types of Complexity
As noted earlier, complexity analysis focuses on either the time or space that an algorithm uses. It allows you to compare different algorithms and choose the best one for your case.
There are two main ways to measure the complexity of an algorithm:
- Time Complexity describes how much time an algorithm takes to run in relation to the input size.
- Space Complexity describes how much space an algorithm takes up during execution in relation to the input size.
Both the time complexity and space complexity are given as functions of the input size, and they do not represent the actual time or space required. They’re used together to assess an algorithm, and there may be trade-offs between space and time.
Learn How to calculate time complexity and How to calculate space complexity.
Asymptotic Notations
Asymptotic notations are the mathematical notations used to describe the time or space complexity of an algorithm based on the input size.
These notations are essentially sets of functions. There are three main notations used:
- Big O notation, which defines an upper bound on the complexity of an algorithm as its input size grows.
- Big Omega notation (Big Ω), which defines a lower bound on the complexity of an algorithm as its input size grows.
- Big Theta notation (Big θ), which defines both an upper and a lower bound on the complexity of an algorithm as its input size grows. Theta notation is said to define a tight bound.
There are lots of websites out there telling people that Big O, Big Theta, and Big Omega are related to the worst, average, and best case analyses of algorithms, respectively. This is not true. These notations define sets of functions and can be individually applied to any type of analysis.
We use these notations to analyze and compare algorithms. If we say that algorithm A’s time complexity has an asymptotic upper bound of O(g(n)), or, more simply, that it is O(g(n)), we mean that this time complexity belongs to the set of complexities upper-bounded by g(n), where n is the input size. That means that the time complexity scales no worse than g(n) with the input size. Usually, unless explicitly stated, we are talking about the worst-case complexity when using asymptotic notations.
Bear in mind that asymptotic notations do not provide the exact running time or space usage of an algorithm. These things are dependent on software implementation and hardware. Instead, they describe how the algorithm scales with the input size.
For example, suppose we have two algorithms for sorting a list of users alphabetically. We can use asymptotic notations to compare these algorithms because we will know how well or how badly they will perform as the number of users increases. However, we won’t know how much time or space each algorithm will take during each execution.
Why do we drop less important terms and coefficients in asymptotic analysis?
In asymptotic analysis, we focus on how fast the complexity of an algorithm grows with the input size. We call this the rate of growth of the algorithm. To keep things manageable, we need to extract only the most important part of the algorithm.
For instance, suppose that an algorithm, running on an input of size n, takes 4n² + 200n + 300 machine instructions, i.e. the time complexity. The 4n² part becomes larger than 200n + 300 once n becomes large enough, 52 in this case. Here’s a chart showing values of 4n² and 200n + 300 for values of n from 0 to 100:
We would say that the running time of this algorithm grows as n², dropping the coefficient 4 and 200n + 300. The coefficient doesn’t matter because, as long as the running time is an² + bn + c, for some numbers a > 0, b, and c, there will always be a value of n for which an² is greater than bn + c, and this difference increases as n increases, regardless of the constants.
By discarding the less important terms and coefficients, we can focus on the significant part of an algorithm — its rate of growth. This simplifies the process of understanding how fast algorithms grow and comparing them.
Big O Notation
We use Big O notation to asymptotically bound the rate of growth of an algorithm from above. Big O simply means “the algorithm will grow at most this much, but it can grow more slowly.”
When we say that the running time of an algorithm is O(g(n)), where g(n) is a function of the input size (time or space complexity), we’re saying that once n becomes large enough, the running time is at most c·g(n), where c is a constant. Here’s a graph to illustrate this:
We say that the running time is “Big O of g(n).” This notation defines an asymptotic upper bound, since it bounds the running time from above for large enough n.
Mathematically, Big O is defined as:
O(g(n)): { f(n) | there exist positive constants c and n0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0 }
If your brain just blue-screened reading that, don’t worry. I’ll try to explain it in a simple way.
This definition means that f(n), which represents the complexity of your algorithm, where n is the input size, is part of the set of complexities upper bounded by g(n) multiplied by a certain constant c. This constant can really be any value that satisfies the constraints that 0 ≤ f(n) ≤ c·g(n) for all values of n greater than or equal to n0, which is the value of n from which 0 ≤ f(n) ≤ c·g(n) will always hold true. g(n) represents the complexity that serves as an upper bound on f(n).
I hope that is a clear enough explanation.
f(n) and g(n) can include or represent any complexities, like log n, n, n², 2^n, and so on.
As an example, suppose the time complexity of an algorithm is 2n + 4. That expression would be f(n) above. Suppose we want to check whether 2n + 4 belongs to O(n), in which case g(n) = n. Now we need to find a value for c such that f(n) ≤ c·g(n), for large enough n.
We could choose any value c ≥ 3 here. As long as there’s a constant that will make g(n) always be greater than or equal to f(n) for large enough n, then the complexity 2n + 4 is said to be O(n).
Here’s a table showing values of 2n + 4 and c·g(n) for values of n from 1 to 5, where c = 3.
As you can see 2n + 4 is less than or equal to 3n for all n ≥ 4. Therefore, 2n + 4 is O(n).
Bear in mind that the Big O notation can describe all complexities that are “below” the specified upper bound, which allows you to make correct but imprecise statements. For example, the binary search algorithm has a worst-case time complexity of log n. I could say that this time complexity belongs to sets like O(n), O(n²), and larger ones. That’s because log n is upper-bounded by those functions, though they do not provide very precise information.
Big Omega Notation (Big Ω Notation)
We use the Big Ω notation to asymptotically bound the rate of growth of an algorithm from below. It means that the algorithm will grow at least as shown but may grow more quickly.
When we say that a running time is Ω(g(n)), where g(n) is a function of the input size n, we mean that the running time is at least c·g(n) for some constant c, for large enough n. Here’s a graph to illustrate this:
We say that the running time is “Big-Ω of g(n).” This notation determines an asymptotic lower bound, as it bounds the growth of an algorithm from below, for large enough input sizes.
Mathematically, Big Omega is defined as:
O(g(n)): { f(n) | there exist positive constants n0 and c such that 0 <= c·g(n) <= for all n >= n0 }
This means that f(n) (the complexity of your algorithm) belongs to the set Ω(g(n)), i.e., the set of complexities lower bounded by g(n), if there is a constant c such that f(n) will always be greater than or equal to c·g(n) for large enough n.
Just like with Big O, we can make correct but imprecise statements using Big Ω. For example, the worst-case time complexity of the linear search algorithm is n. We can say that the worst-case time complexity of such algorithm is Ω(1), because we know that it takes at least constant time, though it is not a very accurate or useful information.
Theta notation (θ notation)
The Big θ notation bounds the rate of growth of an algorithm from both above and below. This means that for large enough input sizes, the algorithm’s complexity is between a lower and an upper bound. Big θ is said to determine a tight bound on the complexity of an algorithm.
When we say that the running time is θ(g(n)), we’re saying that once n gets large enough, the running time is at least c1·g(n) and at most c2·g(n) for some constants c1 and c2. Here’s a graph to illustrate this:
Mathematically, Big θ is defined as:
θ(g(n)): { f(n) | there exist positive constants c1, c2, and n0 such that c1·g(n) ≤ f(n) ≤ c2·g(n) for all n ≥ n0 }
So, f(n) belongs to the set θ(g(n)), if there are positive constants c1 and c2 such that f(n) is between c1·g(n) (lower bound) and c2·g(n) (upper bound) for large enough n.
Unlike Big O and Big Ω, you can’t make imprecise statements with Big θ because it precisely determines how your algorithms grows. We say Big Theta defines an asymptotically tight bound on the complexity. We use “tight” because this notation bounds the complexity between lower and upper boundaries.
Relationship between Big O, Big Theta and Big Omega
Now that you possibly understand what these three notations represent and what they’re used for, let’s see how they relate to each other.
Here’s just a quick recap for the sake of reasoning:
- Big O defines an upper bound on the rate of growth;
- Big Ω defines a lower bound on the rate of growth;
- Big θ defines both a lower and an upper bound — a tight bound — on the rate of growth.
The binary search algorithm takes log n operations to complete in the worst case. We can say that the worst-case running time of the binary search algorithm is θ(log n), but it would be incorrect to say that it runs in θ(log n) time in all cases. We know that the target value may be found on the first iteration, which would be the best case. We can say that the binary search runs in θ(1) time in the best case. Now we know that the running time of the binary search is never worse than θ(log n) but can be better.
We can use the Big O notation to mean that the running time will never grow faster than log n in all cases, which we would represent by O(log n). We can also use Big Ω to mean that the running time will never grow slower than constant time, which we would represent by Ω(1).
Big O is what we use to describe the complexity of an algorithm in all cases. We can say that binary search always runs in O(log n) time.
Because Big θ bounds the running time from both above and below, and Big O bounds only from above, when we say that an algorithm complexity is θ(f(n)), then it is also O(f(n)). Similarly, since Big Ω bounds the running time from below, θ(f(n)) also implies Ω(f(n)).
However, if the running time is O(f(n)), we cannot say it is θ(f(n)). In the same way, Ω(f(n)) does not imply θ(f(n)).
In the case of the binary search algorithm, the worst-case running time is θ(log n), so it is also O(log n) and Ω(log n). We also know that it runs in O(log n) and Ω(1) in all cases. But we cannot say that it runs in θ(log n) or θ(1) in all cases because we know it takes at least constant time and at most log n.
To recap, everything that is in θ(f(n)) is also in O(f(n)) and in Ω(f(n)), but not the other way around. In sets terminology, θ(f(n)) is the intersection of O(f(n)) and Ω(f(n)).
What is the most used notation?
We mostly use Big O. There are several reasons for this:
- Ease of Understanding: Big O is the easiest notation to learn. Think about it. It simply defines that the algorithm’s complexity will not grow more quickly than what it shows.
- Comprehensiveness: If we use Big O together with the worst-case analysis, we can determine how the algorithm scales in all cases. This gives us a high-level sense of which algorithms are fast, which are slow, and what the trade-offs are.
- Standardization: It has become a standard way to discuss and compare algorithmic performance across the field of computer science and beyond.
You’ll see Big O being used pretty much everywhere when talking about algorithm efficiency. It’s a very useful metric for improving software performance.
Asymptotic Analysis Limitations
Before understanding what asymptotic analysis can and cannot do, we have to understand the limitations of experimental analysis.
Experimental analysis involves actually running algorithms and measuring their running times for certain inputs in the same hardware and software environments, and then comparing the results. However, the experiments can be done only on a limited amount of inputs, leaving out inputs whose running times may be important for the analysis.
So, instead, we use asymptotic analysis.
Even though it is not perfect, asymptotic analysis is the best way to analyze and compare algorithms. It gives you an overview of resource (time and space) consumption growth, ignoring details such as constants. Because some details are ignored, sometimes it might be impossible to tell which algorithm is better if they end up having the same time/space complexity.
Additionally, an algorithm may perform well for large inputs, but those large inputs are never actually given to it and an asymptotically slower algorithm that is faster for smaller inputs may be better in this case.
So to recap, while asymptotic analysis is a useful tool for comparing algorithms and provides valuable insights into their performance, it has its limitations. It does not give you exact running times or space usage and ignores sometimes important details such as constants. Moreover, it does not take hardware and implementation details into account, which affect an algorithm’s performance in real-world applications. It also assumes that the input size is the only factor that affects algorithm performance, which is not always the case in practice.
Conclusion
Asymptotic analysis is a useful tool for comparing algorithms based on their time and space complexity. It can measure the best, average, and worst performance of an algorithm using asymptotic notations such as Omega (Ω), Theta (θ), and the well-known Big-O.
Even though complexity analysis is the best method out there for comparing algorithms, it has its limitations. It does not give you exact running times or space usage of algorithms and does not consider constant factors. Moreover, it does not take hardware and software implementations into account. While this is actually a good thing for comparing algorithms, you may need to consider hardware and software depending on your situation.
Recommended Resources
Complexity analysis is a complex topic to understand. Reading a lot of stuff will help you grasp the concepts presented here. And so, I have a list resources to recommend that helped me write this article:
- Programiz (https://www.programiz.com/dsa/asymptotic-notations)
- Khan Academy (https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation). The computer science course is superb in my opinion, especially the asymptotic analysis unit. I recommend you do the exercises, because they will help you a lot.
- Stack Exchange — Explanation of the mathematical definition of Big O (https://math.stackexchange.com/questions/958460/can-someone-explain-the-mathematical-definition-of-bigo)
- Stack Overflow — What is Theta? (https://stackoverflow.com/questions/464078/what-is-the-difference-between-lower-bound-and-tight-bound/471292#471292)
- Stack Overflow — What does Big Ө represent? (https://stackoverflow.com/questions/10376740/what-exactly-does-big-Ө-notation-represent)
- Desmos — Nice website to make graphs. Before using it, remember that you have to use x instead of n when writing the expressions.
Donate
Did you like this article? If you did, please consider buying me a coffee.
