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 ........

 

Posted Date: 4/4/2013 6:21:54 AM | Location : United States

Ask an Expert

Related Discussions:- The complexity ladder, Assignment Help, Ask Question on The complexity ladder, Get Answer, Expert's Help, The complexity ladder Discussions

Write discussion on The complexity ladder
Your posts are moderated

Write your message here..

Related Questions

Find strongly connected components - dfs, A striking application of DFS is ... A striking application of DFS is determine a strongly connected component of a graph. Definition: For graph G = (V, E) , where V refer to the set of vertices and E refer to the

Stack, Explain the array and linked list implementation of stack Explain the array and linked list implementation of stack

Algorithm for similar binary tree, Q. The two Binary Trees are said to be s... Q. The two Binary Trees are said to be similar if they are both empty or if they are both non- empty and left and right sub trees are similar. Write down an algorithm to determine

Find the optimal solution - branch and bound algorithm, Consider the follow... Consider the following 5-city traveling salesman problem. The distance between each city (in miles) is shown in the following table: (a) Formulate an IP whose solution will

State the complex reallocation procedure, State the complex reallocation pr... State the complex reallocation procedure Some languages provide arrays whose sizes are established at run-time and can change during execution. These dynamic arrays have an in

Green computing, In the present scenario of global warming, the computer ha... In the present scenario of global warming, the computer hard ware and software are also contributing for the increase in the temperature in the environment and contributing for the

Data type, Data type An implementation of an abstract data type on a... Data type An implementation of an abstract data type on a computer. Therefore, for instance, Boolean ADT is implemented as the Boolean type in Java, and bool type in C++;

Complexity of quick sort, Q. What do you mean by the best case complexity o... Q. What do you mean by the best case complexity of quick sort and outline why it is so. How would its worst case behaviour arise?

Analyze an algorithm, In order to analyze an algorithm is to find out the a... In order to analyze an algorithm is to find out the amount of resources (like time & storage) that are utilized to execute. Mostly algorithms are designed to work along with inputs

Breadth first search, While BFS is applied, the vertices of the graph are d... While BFS is applied, the vertices of the graph are divided into two categories. The vertices, that are visited as part of the search & those vertices that are not visited as part