The basic concept of Lower Bound Theory
The lower bound theory is used to find the lowest complexity algorithm to solve a problem.
What is the lower bound?
Let us assume L(n) to be the running time of an algorithm A, then g(n) is the lower bound of the algorithm A. If there are two constants C and N, such that
L(n) >= C * g(n), for n > N.
What is the upper bound?
Let us assume U(n) to be the running time of an algorithm A, then g(n) is the upper bound of the algorithm A. If there are two constants C and N, such that
U(n) < = C * g(n) for n > N.
What is the lower bound theory?
The lower bound theory tells us that with the lower bound L(n) of an algorithm, it is not possible for other algorithms with time complexity less than L(n) for random input. This implies that every algorithm must take at least L(n) time in the worst case. L(n) denotes the minimum of every possible algorithm.
The lower bound is necessary for any algorithm as after we have completed it, we can compare it with the actual complexity of the algorithm. If the complexity and the order of the algorithm are the same, then we can declare the algorithm optimal. One of the best examples of optimal algorithms is merge sort. The upper bound should match the lower bound, that is, L(n) = U(n).
The easiest method to find the lower bound is the trivial lower bound method. If we can easily observe the lower bounds on the basis of the number of inputs taken and outputs produced, then it is known as the trivial lower bound method. For example, multiplication of n x n matrix.
Computational model:
The algorithms that are comparison-based uses the computational method. One of the examples that use the computational method is sorting. In sorting, we need to compare the elements and sort them accordingly.
Even in searching, we need to compare the elements, hence it is also a good example of this method.
Various types of computational models are:
- Ordered searching
We use it when the list is already sorted. For example, linear search and binary search.
In linear search, we compare the key element with all the elements in the array one by one. Similarly, in binary search, we compare the elements one by one after dividing them from the middle, keeping smaller values on the left side, and larger values on the right side.
- Sorting
An example of it would be to find the lower bound using a computational model. In the computational model we assume n elements, for n elements, we have a total of n! Combinations.
Reference