2

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?

K-Smoove
  • 21
  • 1
  • 3

2 Answers2

4

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))

David Zwart
  • 431
  • 5
  • 23
rishi kant
  • 1,235
  • 1
  • 9
  • 28
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.

Deepak
  • 275
  • 2
  • 18
  • I realize that the best case scenario is generally not very useful, but I read that the lower bound of an algorithm is important b/c it proves that no algorithm can do better. So does this mean that lower bound and best case are two different things? – K-Smoove Jun 21 '15 at 17:20
  • A typical lower bound proof says that any algorithm to solve a problem must take at least time f(n) - e.g. any sort using only comparisons must make at least n lg n comparisons in the worst case. This is not the same as a best case scenario which might say, for example, that a bubble sort may in the best case only make n comparisons. – mcdowella Jun 21 '15 at 17:26
  • @K-Smoove best case is synonymous to lower bound, or I would say that in best case analysis we will consider the lower bound on running time. – Deepak Jun 22 '15 at 17:05