Lower and Upper bound of an algorithm

Question

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

Answer 1

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

Answer 2

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.