Sunday, May 30, 2004

Why a polynomial algorithm is better than exponential algorithm?

a polynomial algorithm is an algorithm if the complexity function of this algorithm has a rate of growth O(n^k). otherwise it's an exponential algorithm. From a basic mathematical point of view we know why a polynomial algorithm is prefered from an exponential one is pretty simple. When the size of the problem, that is, it's input size grows larger the running time of the exponential algorithm grows way too faster than the polynomial algorithm. This is a very basic observation. But there is also another important property in this comparison that does not get noticed very often. That is when the machine power increases for some reason the limit of the size of the problem that the exponential algorithm can solve increases by a smaller factor (ex: PrevSize+10) where as the exponential algorithm's limit of the size of the problem grows by multiple factors (ex: PrevSize x 10 ). This makes a huge impact and deserves mentioning in this fast growing hardware world.

No comments: