What is the running time of an algorithm?

    Computers are often judged on how many instructions they can complete in a given amount of time.  For example, a 400 MHz Pentium can compete 400 million cycles every second.  Algorithms on the other hand are judged on how much slower they become as the size of their input increases.  Really bad algorithms can work great on small problems, but may become so slow on larger problems that they will never finish in our lifetime.  A good algorithm will experience a modest increase in the time to finish the problem as the size of the problem becomes larger.

    Computer theoretitians generally consider a good algorithm to be anything that can run in a polynomial amount of time.  This means that the rate of increase in the amount of time to complete the problem as the input size increases is no greater than some polynomial.  For example, if n is the number of elements in the input, then the following would be considered acceptable bounds on the time to complete the problem:

We don't actually care about the unit of time here (minutes, seconds, cycles, etc.).  All we care is that the value in front of it is a some kind of polynomial.  In each of the above cases, the problem can have a substantial size, without causing the running time to become unmanagable.  Consider that if n=1000 then, each of the above values is less then 3 days.  Here are some unacceptable bounds on the time to complete a problem: If n appears in the exponent, then it means we are experiencing exponential growth, which means that the amount of time will become prohibitively long when n grows by even a small amount.  Consider that if n > 30 then 2n > 1 billion.  In the last example above, the rate of growth is proportional to the factorial function, which is 1 x 2 x 3 x .... x n.  This rate of growth is even worse than exponential growth.  Consider that if n > 30 then n! > 1 neptillion (which is 1 followed by 30 zeros).  Even the fastest computer on the planet would not be able to execute this many instructions in our lifetme.