[Introduction to Algorithms, CLRS] Exercises 2.2-4

This is a solution for Introduction to Algorithms. I write this for my study purpose.

Exercises 2.2-4

How can we modify almost any algorithm to have a good best-case running time?

Answer:

We can design any algorithm to treat its best-case scenario as a special case and return a predetermined solution.

For example, for selection sort, we can check whether the input array is already sorted and if it is, we will not do anything. So, selection sort will run with a best-case running time of Θ(n).

source: http://atekihcan.github.io/CLRS/E02.02-04/