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

Explain expert system, 1. What is an expert system and where are they need... 1. What is an expert system and where are they needed? 2. What are the major issues involved in building an expert system?

Explain in detail about the abstract data type, Abstract data type The ... Abstract data type The thing which makes an abstract data type abstract is that its carrier set and its operations are mathematical entities, like geometric objects or numbers;

Infix to postfix conversion, A*(B+D)/E-F*(G+H/K) A*(B+D)/E-F*(G+H/K)

Asymptotic notations, types of asymptotic notations types of asymptotic notations

Hashing, explain collision resloving techniques in hasing explain collision resloving techniques in hasing

Explain the halting problem, Explain the halting problem Given a comput... Explain the halting problem Given a computer program and an input to it, verify whether the program will halt on that input or continue working indefinitely on it.

Adjacency multilist of directed graph, I want to study example I want to study example

Determine the warnock algorithm, Warnock's Algorithm A divide and conqu... Warnock's Algorithm A divide and conquer algorithm Warnock (PolyList PL, ViewPort VP) If (PL simple in VP) then Draw PL in VP, else Split VP vertically and horiz

Implement an algorithm to simulate car re-organizing, Design  and implement... Design  and implement  an algorithm  to simulate car  re-organizing of the train at the railway switching junction. You can only use stacks as the data structure to represent the t

Tower of hanoi, how do we use 4-discs stack to solve tower of hanoi problem... how do we use 4-discs stack to solve tower of hanoi problem and write an algorithm to solve it?