Differentiate between polynomial algorithm and exponential algorithm?

Answer 1

Do you mean, "the difference between an algorithm that runs in polynomial time, and one that runs in exponential time".

First a real quick review. A polynomial is any equation of the form

y = cmxm + ... + c2x2 + c1x + c0 ,

where ci are constants

An exponential function is something of the form

y = cx

These functions grow much faster than any polynomial function.

So, if T(n) describes the runtime of an algorithm as a function of whatever (# of inputs, size of input, etc.)., and T(n) can be bound above by any polynomic function, then we say that algorithm runs in polynomial time.

If it can't be bound above by a polynomial function, but can be bound above by an exponential function, we say it runs in exponential time.

Note how ugly an exponential algorithm is. By adding one more input, we roughly double (or triple, whatever c is) the run-time.