6

In mathematics, there are notations for asymptotic lower bounds, upper bounds, and tight (within-a-constant-factor) bounds. When describing the growth of functions in general, it makes sense that all three might be relevant to some function or other.

In algorithm analysis, asymptotic notation is usually used to describe the growth in time or space requirements.

To me, it seems logical that I may be interested in the maximum, the minimum or the expected requirements. Ignoring the expected requirements, I might be interested in the lower bound of the best case (minimum space/time) or the upper bound of the worst case (maximum space/time).

I can't imagine why I should ever be interested in the lower bound of the worst case or the upper bound of the best case. Since the lower bound is a kind of best case and the upper bound a kind of worst case, these seem like "best case of the worst case" and "worst case of the best case" mismatches to me.

But on several occasions, I've had replies to answers/comments that suggest this may be a failure of imagination on my part.

So - what is it that I'm failing to imagine?

I won't consider a statement along the lines of "it's quite common to say that the lower bound of the worst case of the blah algorithm is blah" to answer the question, unless it also says why people care.

2 Answers2

6

The lower bound of the worst case can be used to prove that an algorithm is not going to work for you.

In particular think about real time programming. I need to have my code execute in at most time x because it needs an answer in time to send the right message to a piece of machinery that needs to receive messages on a very precise schedule or else things go wrong. If a lower bound on the worst case exceeds x, then that proves that you absolutely have to think of something better. It doesn't matter if 99.99% of the time you're fine, because that remaining 0.01% of the time could seriously damage something.

btilly
  • 18,290
  • 1
  • 50
  • 76
  • Checking if I understand... I can see that the lower bound of the worst case can prove that the algorithm is (for that worst case) always too slow, but at first sight it seems like an over-strong (and overly hard to prove) way of saying "sometimes too slow". But perhaps "always too slow within the worst case" is sometimes easier to prove? Maybe it makes sense to redefine the worst-case to be more selective until the set of fast-enough cases within that is empty? –  May 07 '11 at 01:12
  • 1
    @Steve314: A lower bound for the worst case is often easier to prove than exact performance for the worst case. Furthermore thinking about those bounds often gives you insight into why it is hard, and therefore what sorts of other ideas you can immediately discard. – btilly May 07 '11 at 01:34
  • 1
    I think I'm happy with this now. If the "worst case" is sometimes, but not always, too slow then there must be greater and lesser degrees of "worst". Choosing to focus on the worst of the worst makes sense. That should naturally lead to an "always" proof, if one is possible. –  May 07 '11 at 01:40
  • 1
    @Steve314: It is worth noting that one often notices a lower bound for the worst case when you were actually looking for an upper bound for the worst case. In other words when trying to show you are in the right track, you sometimes notice that you were on the wrong one. :-) – btilly May 07 '11 at 01:50
  • @Steve314: It is also worth noting that the most important outstanding CS problem is proving that NP-complete problems are not in P. This is a proof of lower bounds for the worst case for a lot of problems. – btilly May 07 '11 at 01:53
0

I'm not sure what the upper bound of the best case would be good for, but at times it may be useful to identify the lower bound for the worst case for the best possible algorithm that could perform a given task. Such information could be useful if one has an algorithm that e.g. runs in time O(N^2lgN) and is trying to decide if one should try to find something better. If one can determine that the lower worst-case bound for an algorithm that can accomplish what needs to be done will be O(N^2lg(lgN)), that would imply that the algorithm one had was close to being within a constant factor of optimal. If instead lower-bound analysis yielded O(lgN), that would suggest that there might possibly be much more room for improvement.

supercat
  • 8,445
  • 23
  • 28