•The run-time of code is usually greater when operating on a
•There can be massive differences in run-time between
different algorithms, even for the same problem.
•Knowing the shape of the run-time growth curve is very
•“Can I wait long enough to get the answer for this input?”
•“Is it even worth writing this code?”
Ways to determine run-time
•Run the code and measure run-time. Run it for different input
sizes to determine the growth curve.
•Estimate run-time “on paper.” Why would you want to do
•Beneﬁts of estimating on paper:
•Can pick among alternative algorithms without having to code
•Can decide if the one we pick is even worth coding up.
•If all we want to know is the shape of the growth curve, a
back-of-the-envelope estimate is ﬁne.