Introduction to asymptotic algorithm classes
We saw in the last article the importance of identifying asymptotic behavior for the algorithm analysis process. In this article we will learn about asymptotic classes. Classes that computer science uses to classify algorithms according to their performance.
We understand that the complexity formula of an algorithm gives us little detail about its efficiency. However, analysis of your asymptotic behavior shows exactly how your performance behaves during its execution.
The secret of the asymptotic behavior of an algorithm lies in the highest polynomial term of its complexity formula, as this term defines its asymptotic class. See below:
Below is a list of the most common asymptotic classes in algorithm analysis.
Efficiency differences between algorithms of the same class
What if two algorithms are of the same asymptotic classe? Which will be the most efficient?
For the analysis of algorithms, what matters is just defining the class of the algorithm, because it defines its asymptotic behavior.
Two algorithms belonging to the same class have the same asymptotic behavior. This means that: small variations in performance between algorithms of the same class are of little importance. Let’s see why:
Imagine two algorithms C and D, both of linear class:
Below is the table with the number of instructions performed by the algorithms for the initial values of n. It is noticed that the algorithm C is more efficient than D, although both are of the same asymptotic class.
Regardless of whether the C algorithm is more efficient than D, this difference in efficiencies will never propagate. Note in the graphs below how the difference in efficiency between them will always remain constant for values other than n.
Note that no matter how large the value of n is, the difference in efficiency between the algorithms of the same asymptotic class will always remain constant. For this reason, the additive and multiplicative constants of the complexity formula are not important for the analysis. In algorithms belonging to the same class, the performance will be very similar for large values of n (n→∞).
Efficiency differences between different class algorithms
In distinct asymptotic class algorithms, the efficiency difference will propagate as the value of n increases. Consider the two algorithms E (quadratic) and F (linear):
Below is the table with the number of instructions performed by the algorithms for the initial values of n. It is noticed that the algorithm F is more efficient than the E.
The interesting thing to note here is that this difference in efficiency between the algorithms propagates as the value of n grows, as these are two algorithms of different asymptotic classes. Notice in the graphs below how the difference in efficiency propagates to values other than n.
Note that as the value of n grows, the efficiency difference between the algorithms becomes increasingly pronounced. Thus, one realizes the importance of asymptotic classes for the analysis process. In algorithms belonging to distinct classes, performance will be greatly impacted by large values of n (n→∞).