Asymptotic classes

Before reading this article, you must have already read the article on asymptotic behavior. If you haven’t read it yet, click here.

We saw in the last article the importance of identifying asymptotic behavior for the algorithm analysis process. In this article we will know the asymptotic classes. Classes that computer science uses to classify algorithms according to their performance.

Introduction to asymptotic classes of algorithms

It has been shown that the T(n) complexity function of an algorithm provides little detail about its efficiency. However, the graphical analysis of its asymptotic behavior can show more accurately how its performance behaves during its execution.

The secret of the asymptotic behavior of an algorithm lies in the highest degree polynomial term of its complexity function, as this term defines its asymptotic class. See below:

In the algorithm:

What really matters is the highest degree term, the n². Therefore, it is a quadratic class algorithm.

In the algorithm:

What really matters is the highest degree term, the n. Therefore, it is a linear class algorithm.

In the algorithm:

What really matters is the highest degree term, the n². Therefore, it is a quadratic class algorithm.

In the algorithm:

What really matters is the highest degree term, the n. Therefore, it is a linear class algorithm

In the algorithm:

What really matters is the highest degree term, the n. Therefore, it is a linear class algorithm.

See below a list of the most common asymptotic classes existing in algorithm analysis.

n!

Factorial

The worst class of algorithm. It usually occurs in some algorithms that use brute force technique to solve problems.

2ⁿ

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.

n^k

Polynomial

They are more efficient than exponentials, but are only suitable for solving small problems. When the value of n grows a lot, the algorithm becomes very inefficient.

n²

Quadratic

Quadratic order polynomials. This class occurs a lot in algorithms that process information in pairs. Usually in nested loops (one loop inside the other).

n log n

Loglinear

Slightly 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 those elements.

log n

Logarithmic

The best of all worlds for algorithms. This class is typical of algorithms that can solve problems by turning them into smaller problems at each step of the solution.

1

Constant

The nirvana of algorithms. In fact, this is a very unlikely situation, as it occurs in algorithms that do not perform any significant computations and therefore are not very useful.

Difference in efficiency within the same class

What if two algorithms are of the same asymptotic class? Which will be the most efficient?

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 not of great importance.

Let’s see why:

Imagine two algorithms C and D, both of linear class:

Algorithm C

Algorithm D

Below is the table with the number of instructions performed by the algorithms for the initial values of n. It can be seen that the C algorithm is more efficient than D, despite both being from the same asymptotic class (the linear class).

Regardless of the fact that algorithm C is more efficient than D, this difference between efficiencies will never propagate. Observe in the graphs illustrated below how the difference in efficiency between both will always remain constant for different values of n.

Note that, regardless of how large the value of n is, the efficiency difference between 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→∞).

In this way, it is clear that, for the analysis of algorithms, what matters is just defining the class of the algorithm, as it defines its asymptotic behavior.

Difference in efficiency in different classes

In algorithms of different asymptotic classes, the difference in efficiency will propagate as the value of n grows. Consider the two algorithms E(quadratic class) and F(linear class):

Algorithm E

Algorithm F

Below is the table with the number of instructions performed by the algorithms for the initial values of n. It is noticed that the F algorithm 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. Observe in the graphs illustrated below how the difference in efficiency between both propagates for different values of n.

Note that, as the value of n grows, the difference in efficiency between the algorithms becomes increasingly pronounced. Therefore, the importance of asymptotic classes for the analysis process is clear. In algorithms belonging to different classes, the performance will suffer a lot of impact for large values of n(n→∞).

Now that you have learned the concepts of asymptotic behavior and asymptotic classes, you can begin to understand the asymptotic notations used to represent the performance of algorithms in computer science.

Click on this link and learning the first notation: Big O notation.