Unit 6 Lesson 3 and Unit 6 Lesson 4 - Reasonable vs Unreasonable Time

This isn’t my area of expertise, so please bear with me.

Slide 46 for Unit 6 - Lesson 3, summarizes.
Polynomial, linear, and log algorithms are reasonable.
Exponential algorithms are unreasonable.

However, in Slide 63 of Unit 6 - Lesson 4 it describes the “traveling salesman problem” as being unreasonable.

Isn’t the algorithm for traveling salesman problem O(n!) which would be polynomial and thus reasonable?

Thanks,
Bill

This is my area of expertise, but I am very old and it was decades ago that I studied these things in earnest.

Unit 6 has been simplified to a large extent. That slide you mention is based on O(n^2) compared to O(2^n). A straightforward comparison.

Traveling Salesman is NP-hard. NP means non-deterministic polynomial time. Hard means don’t hold your breath while the computer runs it. It is believed to grow faster than polynomial but not as fast as exponential. Which might make it a bad example in a simplified presentation.

The algorithm was recently improved Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem | WIRED. You might find that interesting.

Traveling Salesman includes a kicker you may not have considered when you calculated O(n!). And that is that you want the shortest path. Asking for any path is not NP-hard.

Unit 6 Lesson 3 Level 3 is a better example. The question compares 2^n to n^20 (and a few others.) Neither of those two are good choices for a solution. When you compare exponential growth to polynomial growth it is not unusual to see the latter worse than the former in the short term. When we compare O(2^n) to O(n^20) we will see a difference after our computer has been running for a few months, maybe a year. They both get hard to solve real fast. But that makes it a good thing to explore with the students.

I created an App Lab app to explore that with the class when I get to it. Code.org - App Lab
You can experiment with different classes of algorithms by adding new formulas. I have the 4 choices from that question coded up already.

Use the bigger N button to increase the max value of N. As N gets to about 150 we see O(2^n) outgrow O(n^20). Less than that and O(n^20) seems less efficient.

1 Like

Don,

Thank you for the fantastic explanation. as well as the article and the app!

Bill

Did the slide show change? I am prepping this lesson and I see on slide 49 “Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.” That would include Traveling Salesman. because to produce all the potential paths and pick the minimum is O(n!).

I was taught that O(n!) isn’t really the right description. If we decompose n! as n (n - 1) (n -2)…(n - (n - 1)) we can do the math and see the first term is n^n so O(n!) should be called O(n^n). O(n^n) is, in my understanding, the correct notation because the second, third, to nth term grows at a smaller rate.

Having said that I am seeing O(n!) being used as if it is proper to do so. Things change.

1 Like