big o notation

what is big o notation?

measures how no. of steps & memory usage change as the amount of data being processed increases

best case for linear search

o(1)

average case for linear search

o(n)

worst case for linear search

o(n)

best case for binary search array

o(1)

average case for binary search array

o(log n)

worst case for binary search array

o(log n)

best case for binary search tree

o(1)

average case for binary search tree

o(log n)

worst case for binary search tree

o(n)

best case for hashing

o(1)

average case for hashing

o(1)

worst case for hashing

o(n)

best case for breadth/depth first search

o(1)

average case for breadth/depth first search

o(V+E)

no. of vertices + edges

worst case for breadth/depth first search

o(V^2)

best case for bubble sort

o(n)

average case for bubble sort

o(n^2)

worst case for bubble sort

o(n^2)

space complexity of bubble sort

o(1)

best case for insertion sort

o(n)

average case for insertion sort

o(n^2)

worst case for insertion sort

o(n^2)

space complexity of insertion sort

o(1)

best case for merge sort

o(n log n)

average case for merge sort

o(n log n)

worst case for merge sort

o(n log n)

space complexity for merge sort

o(n)

best case for quick sort

o(n log n)

average case for quick sort

o(n log n)

worst case for quick sort

o(n^2)

space complexity for quick sort

o(log n)

o(1)

• constant

• always executes for the same amount of time regardless of the size of the data set

• efficient with any data set

o(log n)

• logarithmic

• rate of increase gets smaller as the amount of data increases time

• halves the data set in each pass

• opposite to exponential

• efficient with large data sets

o(n)

• linear

• grows in proportion to amount of data

• reduces efficiency with increasingly large data sets

o(n log n)

• linearithmic

• divide a data set but can be solved using concurrency on independent divided lists

o(n^2)

• performance proportional to the square of the size of the data set

• significantly reduces efficiency with increasingly large data sets

o(2^n)

• doubles with each addition to the data set in each pass

• opposite to logarithmic

• the rate of increase is at the rate k^n as n increases