Menu
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:
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?
695
The running time of an algorithm or a data structure method typically grows with the input size, although it may also vary for different inputs of the same size. Also, the running time is affected by a lot of factors, such as the hardware environment and the software environment.
To calculate the running time, find the maximum number of nested loops that go through a significant portion of the input. Some algorithms use nested loops where the outer loop goes through an input n while the inner loop goes through a different input m. The time complexity in such cases is O(nm).
Runtime Analysis of Algorithms The fastest possible running time for any algorithm is O(1), commonly referred to as Constant Running Time. In this case, the algorithm always takes the same amount of time to execute, regardless of the input size. This is the ideal runtime for an algorithm, but it's rarely achievable.
Let T1(n), T2(n), … be the execution times for all possible inputs of size n. The worst-case time complexity W(n) is then defined as W(n) = max(T1(n), T2(n), …).
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).
187
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
