Any good info on how to teach about reasonable run time? There is an AP practice question about it. Thanks.
1 Like
Hi @choster,
I think I know which one you’re talking about. I got thrown off by that one and chose the wrong answer. 
Here’s the exact standard, with their definition of “reasonable time”…
I will admit I had to look up what exactly “polynomial” means… https://www.mathsisfun.com/algebra/polynomials.html
There is a code.org optional lesson dedicated to this concept: https://curriculum.code.org/csp-1718/unit4/6/optional/1/
The “Traveling Salesman Problem” is used to exemplify a “hard problem” that has an unreasonable run time. That may be a way for students to experience the concept of an unreasonable run time. To me, this seems to get a bit nitty gritty with the math, but my guess is a problem that does get this mathy will use relatively simple numbers (it’s pretty apparent in the example problem that it’s a simple n^2). The code.org lesson is pretty descriptive at the bottom of what it means to be “reasonable” vs “unreasonable”.
Hope that helps!
Frank
2 Likes
Thank you Frank, for this thorough response! I am still trying to figure out the polynomial aspect though. That is what seems to be most confusing to me.