Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

upper bound, lower bound

What does it mean to prove an upper bound or lower bound to an algorithm?

like image 226
DarthVader Avatar asked Nov 29 '09 23:11

DarthVader


People also ask

What is meant by upper bound and lower bound?

In mathematics, particularly in order theory, an upper bound or majorant of a subset S of some preordered set (K, ≤) is an element of K that is greater than or equal to every element of S. Dually, a lower bound or minorant of S is defined to be an element of K that is less than or equal to every element of S.

What is upper bound with example?

noun Mathematics. an element greater than or equal to all the elements in a given set: 3 and 4 are upper bounds of the set consisting of 1, 2, and 3.


2 Answers

Proving an upper bound means you have proven that the algorithm will use no more than some limit on a resource.

Proving a lower bound means you have proven that the algorithm will use no less than some limit on a resource.

"Resource" in this context could be time, memory, bandwidth, or something else.

like image 189
caf Avatar answered Sep 22 '22 22:09

caf


Upper and lower bounds have to do with the minimum and maximum "complexity" of an algorithm (I use that word advisedly since it has a very specific meaning in complexity analysis).

Take, for example, our old friend, the bubble sort. In an ideal case where all the data are already sorted, the time taken is f(n), a function dependent on n, the number of items in the list. That's because you only have to make one pass of the data set (with zero swaps) to ensure your list is sorted.

In a particularly bad case where the data are sorted in the opposite to the order you want, the time taken becomes f(n2). This is because each pass moves one element to the right position and you need n passes to do all elements.

In that case, the upper and lower bounds are different, even though the big-O complexity remains the same.

As an aside, the bubble sort is much maligned (usually for good reasons) but it can make sense in certain circumstances. I actually use it in an application where the bulk of the data are already sorted and only one or two items tend to be added at a time to the end of the list. For adding one item, and with a reverse-directional bubble sort, you can guarantee the new list will be sorted in one pass. That illustrates the lower bound concept.

In fact, you could make an optimization of the bubble sort that sets the lower bound to f(1), simply by providing an extra datum which indicates whether the list is sorted. You would set this after sorting and clear it when adding an item to the end.

like image 36
paxdiablo Avatar answered Sep 22 '22 22:09

paxdiablo