Asymptotic Complexity Classes and Comparison

What is Time Complexity

Time complexity estimates how an algorithm performs, regardless of the programming language and processor used to run the algorithm. We can calculate time complexity simply by counting the number of statements (especially loops and recursive calls) executed by the code written. This time complexity is defined as a function of the input size n. Usually, we use Big-Oh notation to represent the worst-case time complexity of the algorithm.

What is Asymptotic Complexity Classes

As time complexity is the function of input size n. These functions are used to represent the behavior of the algorithm if the input size increases to a very large number.

There are majorly five types of Complexity Classes:

Constant Functions
Decreasing Functions
Polynomial Functions
Logarithmic Functions
Exponential Functions

Constant Functions

A constant function is a function whose (output) value is the same for every input value.

Example: 1, 10, 50, 1000, 10000, 100000,... (Any positive numerical value)

Decreasing Functions

Decreasing function value decreases if the value of input "n" increases.

Example: $\frac{1}{n}, \frac{1}{n^{2}}, \frac{\log n}{n}, \frac{n}{2^{n}}, . . .$

Polynomial Functions

A polynomial function is a function that involves only non-negative integer powers. Polynomial functions are usually in the form of n^C, where C is a positive non-zero integer (C>0).

Example: n^0.1, n^0.5, n^2.5, n⁵⁰, n¹⁰⁰⁰⁰,...

Linear Function: n
Quadric Function: n²
Cubic Function: n³

Logarithmic Functions

Example: log(n), (log(n))², log(n))¹⁰,...

Exponential Functions

In Exponential functions, the value of function increases drastically if the input value increases. Exponential functions are usually in the form of Cⁿ, where C is a positive non-zero integer (C>1).

Example: 2ⁿ, 3ⁿ, (1.5)ⁿ, 7ⁿ,...

The below graph is representing the complexity classes in time vs input value.