3

I am learning about analysis of algorithms.

I came across the term "upper bound" and "lower bound" in "worst-case" running time of an algorithm.

Are they applicable to only the "worst case" or can be used with other cases also ("average case " and "best case")?

2 Answers 2

0

They are applicable to all cases, but "worst case" is the one most programmers go by because it's just better to always assume the worst case (when designing algorithms).

3
  • So do we consider only the "upper bound" of a "worst case" for analysis of an algorithm? Jan 7, 2015 at 21:06
  • @user3902660 Some people only consider that, yes. Often it may be a better idea to think about other cases as well.
    – user7043
    Jan 7, 2015 at 21:18
  • It depends on the kind of program you're working on. If you're working on a real-time system (e.g. hardware control) or to a lesser extent an interactive application, you'll usually focus on minimizing the upper bound/worst case. For systems where high throughput is the goal, e.g. back-end processing systems, "big data"analysis, number crunching and the like, you're more likely to care about the average case.
    – Jules
    Jan 8, 2015 at 9:23
5

In general, the lower bound is the best case (least amount of work performed) and the upper bound is the worst case (most work the algorithm will have to do). Average case is a probabilistic calculation between upper and lower bounds (the result is not necessarily somewhere in the middle, as sometimes the lower bound is potentially rare - or when probability is not simple to establish).

These bounds are useful generally because they narrow down your consideration to "nothing I do can make this particular algorithm perform better than this bound or worse than this one". So yes, they will be a recurring theme in your future endevours to understand algorithms.

I'd only note that many programs stop dead at worst-case considerations, with just a minor salting of discussion of average-case. It doesn't mean that's all people in various fields consider - it's just all most lower level education classes/books bother to discuss.

2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.