Question

Explain signification of upper and lower complexity bounds.

Answer 1

The Lower and Upper Bound Theory provides a way to find the lowest complexity algorithm to solve a problem. Before understanding the theory, first lets have a brief look on what actually Lower and Upper bounds are.

Lower Bound –

Let L(n) be the running time of an algorithm A, 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. Lower bound of an algorithm is shown by the asymptotic notation called Big Omega (or just Omega).

Upper Bound –

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) >= C*g(n) for n > N. Upper bound of an algorithm is shown by the asymptotic notation called Big Oh(O).