Algorithms, upper/lower bounds, and best/worst case

Question

For algorithms, how are the bounds related to best/worst cases? Is the worst case synonymous with upper bound, and best case synonymous with lower bound? Or can you at least derive one from the other? Or are they not related at all?

Answer 1

In the worst case analysis, we calculate upper bound on running time of an algorithm. We must know the case that causes maximum number of operations to be executed. For Linear Search, the worst case happens when the element to be searched (x in the above code) is not present in the array.Most of the times, we do worst case analysis to analyze algorithms. In the worst analysis, we guarantee an upper bound on the running time of an algorithm which is good information.

In the best case analysis, we calculate lower bound on running time of an algorithm. We must know the case that causes minimum number of operations to be executed. In the linear search problem, the best case occurs when x is present at the first location.The Best Case analysis is bogus. Guaranteeing a lower bound on an algorithm doesn’t provide any information as in the worst case, an algorithm may take years to run.

Answer 2

Yes, it can mean worst case synonymous with upper bound and best case synonymous with lower bound.

Worst-case performance is the most used in algorithm analysis. In the worst-case analysis, we guarantee an upper bound on the running time of an algorithm which is good information. In other words, we must find the execution that causes maximum number of operations to be executed. While in the best-case analysis, we calculate lower bound on running time of an algorithm. We must know the case that causes minimum number of operations to be executed.

Concerning your last question, yes we can use the average-case metric to squeeze/solve for either the worst-case or the best-case scenario. Let O, Θ, Ω represent the worst-case, average-case and best-case scenario, respectively, and f(n) and g(n) two arbitrary functions.

1) If f(n) = O(g(n)) and f(n) = Θ(g(n)) ==> f(n) = Ω(g(n))
2) If f(n) = Ω(g(n)) and f(n) = Θ(g(n)) ==> f(n) = O(g(n))