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

Question

This is a question from Introduction to Algorithms by Cormen et al, but this isn't a homework problem. Instead, it's self-study.

I have thought a lot and searched on Google. The answer that I can think of are:

• Use another algorithm.
• Give it best-case inputs
• Use a better computer to run the algorithm

But I don't think these are correct. Changing the algorithm isn't the same as making an algorithm have better performance. Also using a better computer may increase the speed but the algorithm isn't better. This is a question in the beginning of the book so I think this is something simple that I am overlooking.

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

Answer 1

i just reached to this discussion while looking for an answer. what i think there is only one way to make any algorithm best case by having it a fixed input instead of varing input. if we have an fixed input always the cost and time complexity will always be O(1)

Answer 2

We can modify an algorithm for some special-case conditions, so if the input satisfies that condition, we can output the pre-computed answer. Generally, the best case running time is not a good measure for an algorithm. We need to know how the algorithm performes in worst case.

Answer 3

I think the only way for this problem is the input to the algorithm. Because the cases in time complexity analysis only depend on our input, how complex it is, how much times it tends to run the algorithm. on this analysis, we decide whether our case is best, average or worst. So, our input will decide the running time for an algorithm in every case. Or we can change our algorithm to improve for all cases(reducing the time complexity).

These are the ways we can achieve good best-case running time.

Answer 4

We can sometimes use a randomized algorithm, that makes random choices, to allow a probabilistic analysis and thus improve the running time..

Answer 5

The ways we can modify the algorithm to have a best case running time are:

• If the algorithm is at the point of its purpose/solution , For ex, for an increasing sort , it is already ascending order sorted and so on .
• If we modify the algorithm such that we output and exit for its purpose only hence forcing multiple nested loops to be just one

Answer 6

If we could introduce an instruction for that very algorithm in the computation model of the system itself, we can just solve the problem in one instruction.

But as you might have already discovered that it is a highly unrealistic approach. Thus a generic method to modify any algorithm to have a best case running time is next to impossible. What we can do at max is to apply tweaks in the algorithm for general redundancies found in various problems.

Or you can go naive by taking the best case inputs. But again that isn't actually modifying the algorithm. In fact, introducing the algorithm in the computation system itself, instead of being highly unrealistic, isn't a modification in the algorithm either.

Answer 7

You can modify any algorithm to have a best case time complexity of O(n) by adding a special case, that if the input matches this special case - return a cached hard coded answer (or some other easily obtained answer).

For example, for any sort, you can make best case O(n) by checking if the array is already sorted - and if it is, return it as it is.

Note it does not impact average or worst cases (assuming they are not better then O(n)), and you basically improve the algorithm's best case time complexity.

---

Note: If the size of the input is bounded, the same optimization makes the best case O(1), because reading the input in this case is O(1).