The complexity Ladder:
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).
Constant growth. Does
not grow as a function
of n. For example, accessing array for one element A[i]
Looping over n
elements, of an array of size n (normally).
O(n log n)
Worst time case for
insertion sort, matrix multiplication
Table 1: Comparison of several algorithms & their complexities