# In complexity, why do we find upper bounds, not lower bounds?

In algorithms we use to find Big-O (upper bound), Big-omega (lower bound) and Big-Theta but why we are always interested in finding upper bounds instead of lower bounds?

• I do not understand your question. You are saying yourself that we use Big- omega for lower bound, in the same sentence you assert that we are not interested in it. The fact is that we are often more interested in asymptotic upper bound because that is what tells us, to a large extent (though not always) whether the algorithmic technique used will scale up to larger variants of the problem. – babou Jul 11 '15 at 9:23

Lower bounds are of great interest and an active topic of research. However, we tend to be interested in lower bounds for problems and upper bounds for algorithms.

An upper bound for an algorithm is a performance guarantee: the algorithm will not use more than such-and-such an amount of memory or processing steps when run on an input of a particular size. On the other hand, lower bounds for algorithms aren't especially interesting, since most algorithms can be modified to be fast on certain instances and knowing that an algorithm might terminate very quickly isn't often a useful guarantee.

Conversely, any algorithm is an upper bound for the problem it solves. Lower bounds for problems, on the other hand, tell you whether it's worthwhile looking for a faster algorithm than the one you already have. Examples of lower bounds you'll probably be familiar with are completeness results (especially NP-completeness) and the fact that comparison-based sorting takes time $\Omega(n\log n)$.

• In your second paragraph, I think you confound "upper bound" with "worst case". Having (good) lower bounds and upper bounds for the same case describes the performance of an algorithm better than just one. That's particularly important when comparing algorithms. – Raphael Jul 12 '15 at 9:41

It isn't true that we are are more interested in upper bounds than lower bounds.

Knowing the upper bound allows you to estimate whether your algorithm is feasible for a particular application. This is very important in practice which is why you might see upper bounds more often.

However, lower bounds are of great interest as well. Lower bounds tell you whether you can improve your algorithm: when you find a lower bound equal to the upper bound you know your algorithm is optimal. A lower bound might also tell you that a particular problem isn't feasible to solve and you need to make simplifications.

There are many theories dedicated to finding lower bounds in a variety of situations: the $\Omega(n\log n)$ lower bound for sorting (which is used to give lower bounds for other problems like Convex Hull), $NP$-completeness (and other complexity classes), $3$-SUM, Halting Problem, Fischer-Lynch-Paterson,...

• "when you find a lower bound equal to the upper bound you know your algorithm is optimal" -- if that lower bound is for the problem, yes. A lower bound on the runtime of the algorithm does not give you that. – Raphael Jul 12 '15 at 9:43

upper bounds are much easier to determine than lower bounds. lower bounds are one of the great open questions in computer science subject to massive active research. so upper bounds can be regarded as "the path of least resistance" or "low hanging fruit". so far we cannot prove even simple lower bounds on many seemingly basic problems. the problem of (nontrivial/ nonweak/ "strong") lower bounds is so difficult that many scientists refer to the challenge in terms of disappointment and frustration at lack of progress over many decades despite intense research effort by top experts. eg in the standard textbook by Arora/ Barak lower bounds are referred to as "Complexity Theory's Waterloo".

another emerging pov is that upper and lower bounds are often interrelated by many subtle theorems. in many cases by proving one, one can prove the other. this seems a deep recurring principle that hasnt yet been fully understood/ uncovered & may be a key to future progress/ success in the area. some think that some basic principle/ concept in computer science (regarded by many as still "young") is yet to be uncovered that might unlock progress in the area.

another case study is P vs NP which is essentially/ nearly the foremost problem of the field, oriented around difficulty of lower bounds. the concept of "barriers" is relevant; a significant/ deep principle called "natural proofs" for example is regarded as a very difficult, so far insurmountable barrier to overcome to prove nontrivial lower bounds.