Data Structures and Algorithms - Old Questions

11. Explain the use of Big O notation in analyzing algorithms. Compare sorting time efficiencies of Quick-Sort and Merge-Sort.

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.

Quick-Sort vs Merge-Sort

Merge sort is more efficient and works faster than quick sort in case of larger array size or datasets.
whereas
Quick sort is more efficient and works faster than merge sort in case of smaller array size or datasets.

Merge sort has the following performance characteristics:

• Best case: O(n log n)
• Average case: O(n log n)
• Worst case: O(n log n)

Quicksort has the following performance characteristics:

• Best case: O(n)
• Average case: O(n log n)
• Worst case: O(n2)