The complexity ladder, Data Structure & Algorithms

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(log2 (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(n2)  < O(n3), ... , 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







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
Related Questions
Regis lives in Brazil and frequently travels to USA, Japan and Europe. He wants to be able to convert Brazilian Reais into US dollars, European euros and Japanese yen. Conversion f


using a program flowchart design a program to illustrate pop and push operation

Big oh notation (O) : The upper bound for the function 'f' is given by the big oh notation (O). Considering 'g' to be a function from the non-negative integers to the positive real

create a flowchart that displays the students average score for these quizzes

what algorithms can i use for the above title in my project desing and implmentation of road transport booking system

In assignment, you have already started the process of designing a database for the Beauty Salon mini-case (enclosed again below), mainly in the phase of conceptual database design

In this unit, the following four advanced data structures have been practically emphasized. These may be considered as alternative to a height balanced tree, i.e., AVL tree.

A binary tree is a special tree where each non-leaf node can have atmost two child nodes. Most important types of trees which are used to model yes/no, on/off, higher/lower, i.e.,

Abstract Data Types :- A useful tool for specifying the logical properties of a data type is the abstract data type or ADT. The term "abstract data type" refers to the basic mathem