The complexity Ladder:
- T(n) = O(1). It is called constant growth. T(n) does not raise at all as a function of n, it is a constant. For illustration, array access has this characteristic. A[i] takes the identical time independent of the size of the array A.
- T(n) = O(log2 (n)). It is called logarithmic growth. T(n) raise proportional to the base 2 logarithm of n. In fact, the base of logarithm does not matter. For instance, binary search has this characteristic.
- T(n) = O(n). It is called linear growth. T(n) linearly grows with n. For instance, looping over all the elements into a one-dimensional array of n elements would be of the order of O(n).
- T(n) = O(n log (n). It is called nlogn growth. T(n) raise proportional to n times the base 2 logarithm of n. Time complexity of Merge Sort contain this characteristic. Actually no sorting algorithm that employs comparison among elements can be faster than n log n.
- T(n) = O(nk). It is called polynomial growth. T(n) raise proportional to the k-th power of n. We rarely assume algorithms which run in time O(nk) where k is bigger than 2 , since such algorithms are very slow and not practical. For instance, selection sort is an O(n2) algorithm.
- T(n) = O(2n) It is called exponential growth. T(n) raise exponentially.
In computer science, Exponential growth is the most-danger growth pattern. Algorithms which grow this way are fundamentally useless for anything except for very small input size.
Table 1 compares several algorithms in terms of their complexities.
Table 2 compares the typical running time of algorithms of distinct orders.
The growth patterns above have been tabulated in order of enhancing size. That is,
O(1) < O(log(n)) < O(n log(n)) < O(n2) < O(n3), ... , O(2n).
Notation
|
Name
|
Example
|
O(1)
|
Constant
|
Constant growth. Does
|
|
|
not grow as a function
of n. For example, accessing array for one element A[i]
|
O(log n)
|
Logarithmic
|
Binary search
|
O(n)
|
Linear
|
Looping over n
elements, of an array of size n (normally).
|
O(n log n)
|
Sometimes called
"linearithmic"
|
Merge sort
|
O(n2)
|
Quadratic
|
Worst time case for
insertion sort, matrix multiplication
|
O(nc)
|
Polynomial,
sometimes
|
|
O(cn)
|
Exponential
|
|
O(n!)
|
Factorial
|
|
Table 1: Comparison of several algorithms & their complexities
Array size
|
Logarithmic:
log2N
|
Linear: N
|
Quadratic: N2
|
Exponential:
2N
|
8
128
256
1000
100,000
|
3
7
8
10
17
|
8
128
256
1000
100,000
|
64
16,384
65,536
1 million
10 billion
|
256
3.4*1038
1.15*1077
1.07*10301
........
|