Reasonable Run Time

aptest

#1

Any good info on how to teach about reasonable run time? There is an AP practice question about it. Thanks.


#2

Hi @choster,

I think I know which one you’re talking about. I got thrown off by that one and chose the wrong answer. :frowning:

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


#3

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.