Reasonable Run Time



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


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…

There is a optional lesson dedicated to this concept:

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 lesson is pretty descriptive at the bottom of what it means to be “reasonable” vs “unreasonable”.

Hope that helps!



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.