the complexity ladder tn o1 it is called

Question

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(log₂ (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(n²)  < O(n³), ... , 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 ........