The Resources Limit Computation
A computation’s execution time (how long it runs) is specified in terms of the amount of data it is given …
- A problem that runs for a minute on a given amount of data, and runs for two minutes on twice as much data, etc. is said to be a “linear computation”
- Computing the weekly pay and deductions for employees is an example because twice as many employees would take twice as long to compute pay and deductions
Other ways of specifying execution time are possible, such as guesses per interval size as in Day Finder
- Required 5 guesses to find a day among 32 things
- How many guesses would it take if an interval had 64 items?
- How many for 128 items?
- Double the interval use only one more guess … logarithmic