ufsupreme.blogg.se

Note that our main motive is to get an optimal algorithm, which is the one having it’s Upper Bound Same as its Lower Bound (U(n)=L(n)). So in this section, we will be discussing techniques for finding the lower bound of an algorithm. Once we calculated it, then we can compare it with the actual complexity of the algorithm and if their order is the same then we can declare our algorithm as optimal. The Lower Bound is very important for any algorithm. Note that L(n) here is the minimum of all the possible algorithms, of maximum complexity.

Also, every algorithm must take at least L(n) time in the worst case. Upper bound of an algorithm is shown by the asymptotic notation called Big Oh(O) (or just Oh).Īccording to the lower bound theory, for a lower bound L(n) of an algorithm, it is not possible to have any other algorithm (for a common problem) whose time complexity is less than L(n) for random input. Let U(n) be the running time of an algorithm A(say), then g(n) is the Upper Bound of A if there exist two constants C and N such that U(n) N. Lower bound of an algorithm is shown by the asymptotic notation called Big Omega (or just Omega). Let L(n) be the running time of an algorithm A(say), then g(n) is the Lower Bound of A if there exist two constants C and N such that L(n) >= C*g(n) for n > N. Before understanding the theory, first, let’s have a brief look at what actually Lower and Upper bounds are. The Lower and Upper Bound Theory provides a way to find the lowest complexity algorithm to solve a problem.