Question

Does every algorithm have a running-time equation? In other words, are the upper and lower bounds for the running time (on any specified class of inputs) always the same?

Answer 1

The running time of an algorithm is not only a function only of input size (n) but also a function of the input and various running time measurements that weu can define as functions of n. The running time of an algorithm typically grows with the input size, although it may also vary for different inputs of the same size. Every algorithm should have at least some inputs so, it should have a running-time equation.

• Lower Bound :
  If f(n) be the running time of an algorithm, then g(n) will be the Lower Bound of that algorithm if there exist two constants K1 and N such that f(n) >= K1*g(n) for n > N. It is shown by the asymptotic notation called Big Omega or only Omega. This is known as the best case of any algorithm.
• Upper Bound :
  If f(n) be the running time of an algorithm, then g(n) will be the Lower Bound of that algorithm if there exist two constants K2 and N such that f(n) <= K2*g(n) for n > N. Upper bound of an algorithm is shown by the asymptotic notation called  Big-O or only Oh notation. This notation is known as the worst case of an algorithm.

So, both upper bound value and lower bound values are different. Our basic intention is to find an optimal algorithm, where upper bound will be  same as its lower bound .