Q56: Tweaking the Bubble Sort

Question #56: In the inner loop of bubble sort algorithm [refer Q55], let’s say we add a check to break the outer loop if there were no interchanges in the full run of the inner loop. Will the best case of bubble sort improve?

Options:

1. There will be improvement in running time but not asymptotically.
2. Yes, from O(n²) to O(n log(n))
3. Yes, from O(n log(n)) to O(n)
4. Yes, from O(n²) to O(n)

Solution: The best case is when all of the elements are already sorted. In this case, at the end of inner loop for the first time, there will be no exchanges. Hence, the outer loop will terminate in just O(n). So, correct answer is 4th one.