Compare Algorithms Using Asymptotic Relations

In computational complexity, algorithms are classified by their behavior for large inputs, typically taken to be at infinity. Two algorithms are compared by whether the runtime of one is AsymptoticLessEqual (big ), AsymptoticLess (little ), AsymptoticGreaterEqual (big ) or AsymptoticGreater (little ) the other's runtime.

The traveling salesperson problem (TSP) consists of finding the shortest route connecting cities. A naive algorithm is to try all routes. The HeldKarp algorithm improves that to roughly steps. Show that and hence the HeldKarp algorithm is faster.

Both algorithms show that the complexity class of TSP is no worse than EXPTIME, which are problems that can be solved in time . For example, for any , so the HeldKarp algorithm has exponential runtime.

For the factorial function, a linear exponential does not suffice because .

However, the factorial still has exponential runtime because .

Approximate solutions can be found in time, so the approximate TSP is in the complexity class P of problems solvable in polynomial time. Any polynomial algorithm is faster than an exponential one, or .

Related Examples

de es fr ja pt-br zh