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

I have actually thought a lot and also searched top top Google. The answer that I can think that are:

Use one more algorithm.Give the best-case inputsUse a far better computer to run the algorithm

But i don"t think these room correct. Transforming the algorithm isn"t the exact same as make an algorithm have far better performance. Likewise using a far better computer may rise the speed yet the algorithm isn"t better. This is a inquiry in the start of the publication so i think this is something simple that i am overlooking.

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

So how can we modify virtually any algorithm to have a an excellent best-case to run time?



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

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

Note the does not impact average or worst cases (assuming they room not far better then O(n)), and you basically boost the algorithm"s ideal case time complexity.

Note: If the dimension of the entry is bounded, the same optimization makes the best case O(1), due to the fact that reading the input in this case is O(1).


If we might introduce an instruction for that really algorithm in the computation version of the mechanism itself, we deserve to just settle the problem in one instruction.

But as you might have currently discovered the it is a highly unrealistic approach. For this reason a generic an approach to modify any kind of algorithm to have a finest case to run time is alongside impossible. What we can do in ~ max is to apply tweaks in the algorithm for general redundancies uncovered in miscellaneous problems.

Or you deserve to go naive by acquisition the finest case inputs. However again that isn"t actually editing and enhancing the algorithm. In fact, introducing the algorithm in the computation system itself, rather of being very unrealistic, isn"t a change in the algorithm either.


The ways we deserve to modify the algorithm to have a ideal case running time are:

If the algorithm is at the allude of that is purpose/solution , for ex, for an enhancing sort , it is currently ascending bespeak sorted and so top top . If us modify the algorithm such that we output and also exit for its objective only hence forcing lot of nested loops come be just one

We deserve to sometimes usage a randomized algorithm, that renders random choices, to permit a probabilistic analysis and therefore improve the to run time..

I think the only means for this difficulty is the input come the algorithm. Since the instances in time complexity evaluation only count on ours input, how complex it is, just how much time it tends to run the algorithm. ~ above this analysis, we decide whether our case is best, median or worst.So, ours input will certainly decide the to run time for an algorithm in every case.Or us can adjust our algorithm to enhance for all cases(reducing the time complexity).

These are the methods we have the right to achieve good best-case running time.

We can modify one algorithm for some special-case conditions, therefore if the input satisfies the condition, we have the right to output the pre-computed answer. Generally, the ideal case running time is no a great measure for an algorithm. We must know exactly how the algorithm performes in worst case.

i just reached come this conversation while looking for an answer. What ns think there is just one way to make any algorithm finest case by having actually it a addressed input instead of varing input. If we have actually an fixed input constantly the cost and time intricacy will constantly be O(1)

Thanks because that contributing an answer to stack Overflow!

Please be certain to answer the question. Administer details and also share your research!

But avoid

Asking for help, clarification, or responding to other answers.Making statements based on opinion; ago them up with references or an individual experience.

See more: The Jelly Like Substance In The Cell Is Called As, Cytoplasm Function

To discover more, view our tips on writing an excellent answers.

post Your price Discard

By clicking “Post your Answer”, friend agree come our terms of service, privacy policy and also cookie policy

Not the prize you're looking for? Browse various other questions tagged algorithm or questioning your very own question.

site style / logo © 2021 stack Exchange Inc; user contributions license is granted under cc by-sa. Rev2021.11.5.40661

your privacy

By clicking “Accept every cookies”, you agree stack Exchange can store cookie on your machine and disclose info in accordance through our Cookie Policy.