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



Ans: Guess an answer
Verify that it is correct, in that case stop.
Otherwise run the original algorithm.
OR
Check whether the input constitutes an input at the very beginning
Otherwise run the original algorithm.