Algorithms

Upper and Lower bound of a function

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

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


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 npasses to do all elements.