The complexity ladder, Data Structure & Algorithms

Assignment Help:

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

........

 


Related Discussions:- The complexity ladder

Shortest path dijkstras algorithm, * Initialise d & pi* for each vertex ...

* Initialise d & pi* for each vertex v within V( g ) g.d[v] := infinity  g.pi[v] := nil g.d[s] := 0; * Set S to empty * S := { 0 }  Q := V(g) * While (V-S)

Process of in-order traversal, In-order Traversal  This process when ex...

In-order Traversal  This process when executed iteratively also needs a stack and a Boolean to prevent the implementation from traversing any portion of a tree twice. The gener

Functions for inserting and deleting at either of the end, Q. Develop a rep...

Q. Develop a representation for a list where insertions and deletions can be done at either end. Such a structure is known as a Deque (Double ended queue). Write functions for inse

Explain complexity of an algorithm, Complexity of an Algorithm An algo...

Complexity of an Algorithm An algorithm is a sequence of steps to solve a problem; there may be more than one algorithm to solve a problem. The choice of a particular algorith

Two broad classes of collision resolution techniques, Two broad classes of ...

Two broad classes of collision resolution techniques are A) open addressing and B) chaining

Sorting on several keys, Thus far, we have been considering sorting depend ...

Thus far, we have been considering sorting depend on single keys. However, in real life applications, we may desire to sort the data on several keys. The simplest instance is that

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

Branch and bound algorithm, Suppose we have a set of N agents and a set of ...

Suppose we have a set of N agents and a set of N tasks.Each agent can only perform exactly one task and there is a cost associated with each assignment. We would like to find out a

Procedures, what is far and near procedures in system programming?

what is far and near procedures in system programming?

Single pointer pointing to the tail of the queue, Can a Queue be shown by c...

Can a Queue be shown by circular linked list with only single pointer pointing to the tail of the queue? Yes a Queue can be shown by a circular linked list with only single p

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd