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
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 function value decreases if the value of input "n" increases.
A polynomial function is a function that involves only non-negative integer powers. Polynomial functions are usually in the form of nC, where C is a positive non-zero integer (C>0).
Example: n0.1, n0.5, n2.5, n50, n10000,...
- Linear Function: n
- Quadric Function: n2
- Cubic Function: n3
Example: log(n), (log(n))2, log(n))10,...
In Exponential functions, the value of function increases drastically if the input value increases. Exponential functions are usually in the form of Cn, where C is a positive non-zero integer (C>1).
Example: 2n, 3n, (1.5)n, 7n,...
The below graph is representing the complexity classes in time vs input value.
Comparison of values of Asymptotic Complexity Classes
Decreasing Functions < Constant Function < Logarithmic Functions < Polynomial Functions < Exponential Functions
Here are some examples of Complexity classes comparisons:
- n! < nn
- (log(n))2 < n
- (log(n))3 < n
- (log(n))1000 < n
- (log(n))log(n) > n
Ques: Consider one more example with four functions given below and write in increasing order.
F1 = 10
F3 = log(n)
Sol: Increasing order for the given functions is F4 < F1 < F3 < F2
We will see more examples with explanations in the next article.