I Polynomial vs. Exponential time

[senmeis]

Hi,

How much time difference can be expected between polynomial and exponential time?

 

[DaveC426913]

Guessing OP is referring to solving times, like sorting algorithms.

Algorithms with polynomial run times proceed at a manageable rate, whereas algorithms with exponential run times often double their run times with each additional element, rapidly becoming unmanageable.

 

[fresh_42]

Hi,

How much time difference can be expected between polynomial and exponential time?

This is only relevant for large input lengths. An example. Strassen's matrix multiplication has brought the number of multiplications, which were time-consuming in relation to additions, from $n^3$ to $n^{2.8}$. I've heard rumors that this was enough to implement the algorithm in airplane software. And this was only a polynomial improvement.

If you look at NP complete problems like the travelling salesman problem, which has many real-world applications like staffing in industries such as airlines, hospitals, or logistics, where a large number of persons and regulations have to be juggled, you get a tremendous benefit between polynomial and exponential.

$100^5=10^{10}$ but $e^{100}\sim 10^{43}=1000\cdot 10^{10}\cdot 10^{10}\cdot 10^{10}\cdot 10^{10}.$ So even $n=100$ can vary between doable and hopeless.