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

Need help with working out. I dont really get it, Suppose there are exactly...

Suppose there are exactly five packet switches (Figure 4) between a sending host and a receiving host connected by a virtual circuit line (shown as dotted line in figure 4). The tr

Matrices multiplication, Write an algorithm for multiplication of two spars...

Write an algorithm for multiplication of two sparse matrices using Linked Lists.

Write the algorithm to find input and output value, This algorithm inputs 5...

This algorithm inputs 5 values and outputs how many input numbers were positive and how many were negative. Data to be used: N = 1, -5, 2, -8, -7

Explain almost complete binary tree, Almost Complete Binary Tree :-A binary...

Almost Complete Binary Tree :-A binary tree of depth d is an almost whole binary tree if: 1.Any node and at level less than d-1 has two children. 2. for any node and in the tree wi

Sorting algorithm for singly linked lists, Q. Which sorting algorithm can b...

Q. Which sorting algorithm can be easily adaptable for singly linked lists? Explain your answer as well.        Ans: The simple Insertion sort is sim

Nothing, c++ To calculate the amount to be paid by a customer buying yummy ...

c++ To calculate the amount to be paid by a customer buying yummy cupcakes for his birth day party

Postorder traversal of a binary tree, Postorder traversal of a binary tree ...

Postorder traversal of a binary tree struct NODE { struct NODE *left; int value;     /* can take any data type */ struct NODE *right; }; postorder(struct NODE

Data mining, hello, i need help in data mining assignment using sas em and...

hello, i need help in data mining assignment using sas em and crisp-dm

Explain time complexity, Time Complexity:- The time complexity of an algori...

Time Complexity:- The time complexity of an algorithm is the amount of time it requires to run to completion. Some of the reasons for studying time complexity are:- We may be in

What are the advantages of using assertions, Using Assertions When writ...

Using Assertions When writing code, programmer must state pre- and subtle post conditions for public operations, state class invariants and insert unreachable code assertions a

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