Data Structures and Algorithms - Old Questions

11. What is Big ‘O’ notation? Analyze any one sorting algorithm.

Big-O notation is a metrics used to find algorithm complexity. Basically, Big-O notation signifies the relationship between the input to the algorithm and the steps required to execute the algorithm.

A function f(n) is said to be “big-Oh of  g(n)” and we write, f(n)=O(g(n)) or simply f=O(g), if there are two positive constants c and n0 such that f(n)<=c*g(n) for all n>=n0.

E.g. The big oh notation of  f(n)=n+4 is O(n) since n+4<=2n for all n>=4.

The big oh notation of  f(n)=n2+3n+4 is O(n2) since n2+3n+4<=2n2  for all n>=4.

Big O notation specifically describes worst case scenario. It represents the upper bound running time complexity of an algorithm.

__________________________________________

Analysis of Selection Sort

Time Complexity:

The selection sort makes first pass in n-1 comparison, the second pass in n-2 comparisons and so on.

Time complexity = (n-1) + (n-2) + (n-3) + …………………………. +2 +1

= O(n2)

Space Complexity:

Since no extra space besides 5 variables is needed for sorting

Space complexity = O(n)