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 divide and conquer algorithms, Explain divide and conquer algorithm... Explain divide and conquer algorithms  Divide  and  conquer  is  probably  the  best  known  general  algorithm  design  method.  It   work according to the following general p

State the range of operation of abstract data type, State the range of oper... State the range of operation of ADT Operations of the Range of T ADT includes following, where a, b ∈ T and r and s are values of Range of T: a...b-returns a range value (an

Hash clash, Q. What do you understand by the term by hash clash? Explain in... Q. What do you understand by the term by hash clash? Explain in detail any one method to resolve the hash collisions.

What are stored and derived attributes, What are stored and derived attribu... What are stored and derived attributes?  Stored attributes: The attributes kept in a data base are called stored attributes.  Derived attributes: The attributes that are

Complexity of an algorithm, Q. Explain the complexity of an algorithm?  Wha... Q. Explain the complexity of an algorithm?  What are the worst case analysis and best case analysis explain with an example.

Arithmetic expression, How to convert infix postfix and prefix?? How to convert infix postfix and prefix??

Define the internal path length, Define the Internal Path Length The In... Define the Internal Path Length The Internal Path Length I of an extended binary tree is explained as the sum of the lengths of the paths taken over all internal nodes- from th

Abstract data type- queue, A significant aspect of Abstract Data Types is t... A significant aspect of Abstract Data Types is that they explain the properties of a data structure without specifying the details of its implementation. The properties might be im

Write procedure to the insert a node into the linked list, Q. Write a proce... Q. Write a procedure to the insert a node into the linked list at a particular position and draw the same by taking an example?

Explain the term heuristics searching, (a) Discuss the role played by Busin... (a) Discuss the role played by Business Intelligence Systems in giving companies strategic advantage. (b) Explain the term heuristics searching . (c) With the use of an appr