Asymptotic classes (algorithm analysis)

Continue to deepen your knowledge of algorithm analysis. Learn about asymptotic classes and the differences in performance between them.

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.

If you still do not know what is “the asymptotic behavior” of an algorithm, click this link and visit the article where we explain in detail about it.

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:

In the algorithm:
What really matters is the higher degree term, n2. So it’s a quadratic class algorithm.
In the algorithm:
What really matters is the higher degree term, n. So it’s a linear class algorithm.
In the algorithm:
What really matters is the higher degree term, n2. So it’s a quadratic class algorithm.
In the algorithm:
What really matters is the higher degree term, n. So it’s a linear class algorithm.
In the algorithm:
What really matters is the higher degree term, n. So it’s a linear class algorithm.

Below is a list of the most common asymptotic classes in algorithm analysis.

n!
Factorial
The worst category. Usually occurs in some algorithms that use brute force technique to solve problems.
2n
Exponential
More efficient than factorial, but still far from being an efficient algorithm. It also occurs in algorithms that use brute force to solve problems.
nk
Polynomial
They are far more efficient than exponentials, but they are only suitable for solving small problems. When the value of n grows a lot, the algorithm becomes quite inefficient.
n2
Quadratic
Quadratic order polynomials. This class occurs a lot in algorithms that process information in pairs. Usually in nested loops(one loopwithin the other).
n log n
Logarithmic linear
A little less efficient than linear ones. This is a typical asymptotic class of algorithms that implement the “divide-and-conquer” paradigm.
n
Linear
Very efficient algorithm. The linear class occurs in algorithms that need to process n input elements and do small computations on these elements.
log n
Logarithmic
The wonderful class for algorithms. This class is typical of algorithms that can solve problems by turning them into minor problems with each step of the resolution.
1
Constant
The nirvana for the algorithms. In fact, this is a very unlikely situation, as it occurs in algorithms that do not perform any significant computation and therefore do not have much utility.

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:

C algorithm
D algorithm

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):

E algorithm
F algorithm

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→∞).

To dig deeper into algorithm analysis and learn about asymptotic notations, click here and go to the article where we explain you in detail about the first notation. The Big O notation.

Share this article

Share on whatsapp
WhatsApp
Share on facebook
Facebook
Share on twitter
Twitter
Share on linkedin
LinkedIn
Share on email
Email

Follow us
on our social media.