Unit 5 Lab 3: Timing Experiments, Page 4

EK: 4.2.1A, 4.2.1B, 4.2.1C, 4.2.1D

Classifying Algorithms

General note: switch "average time" to "time function" for next pass at this lab. Also be careful to avoid language like "10 times" because "time" is being used in a specific way here.

The average time reporter inputs a function, and a count with a number of test runs. It outputs the average time it takes to run the function, in milliseconds:

You may have created average time on the previous page. If you didn't, open this script.

This says the alphie way of adding the integers from 1 to 100, through 10 runs of the function, took an average of 12.8 milleseconds.

Experiment with average time on algorithms you've built like alphie way, betsy way, factorial, find in unsorted list, find in sorted list, and any others you have handy. What happens to the average time if you double the size of the input?

You can classify algorithms by the amount of time they take to run. At a basic level, many problems can be solved in a reasonable time, while others cannot, even for small input sizes.

Here are two blocks to build in Snap!. Build the blocks, then determine which block's algorithm can be solved in a reasonable time, and which cannot. Use the block, found in this project.

The list of 2-digit numbers goes from 10 to 99. There's a math operations block that can give you powers of 10.

Ways to Think About It

To classify an algorithm, look at the number of steps it takes to complete the algorithm, compared to the size of the input.

Note that the following categories say that an algorithm takes at most so much time. So, for example, a constant-time algorithm is also a linear-time algorithm, and also a polynomial-time algorithm, and also an exponential-time algorithm. But usually if someone says an algorithm takes linear time, they mean that it takes more than constant time but not less than linear time.

Some algorithms take the same number of steps, even as the input grows. These algorithms take constant time.
Some algorithms take a number of steps proportional to the input size. (If you double the size of the input, the number of steps doubles also.) These algorithms take linear time.

Polynomial time can be further broken down, depending on the polynomial. Algorithms whose runtime is about n² run in quadratic time. (If you double the size of the input, that quadruples the number of steps.) It's rare in practice to find polynomial time algorithms that take more than cubic (n³) time.

If the number of steps is less than or equal to a polynomial function of the size of the input (including a linear function), the algorithm takes polynomial time and is reasonable.
If the number of steps is an exponential function of the size of the input (or another function larger than any polynomial), we say that the algorithm takes an unreasonable amount of time. For an algorithm that takes 2ⁿ time, just adding 1 to the input size doubles the number of steps!

It's important to recognize that an unreasonable algorithm still solves a problem correctly! It just takes an unreasonably long time. Unreasonable algorithms can sometimes be replaced by heuristics, simpler algorithms that may not succeed in solving the problem but serve as reasonable approximations.

Look at some algorithms you've built. Determine whether each algorithm runs in constant time, linear time, polynomial time, or unreasonable time.

For Alphie's way of adding integers, create a graph with the number of integers on the horizontal and the runtime on the vertical. Generate data for the graph by running average time with large numbers (say, multiples of 100). Then use the techniques from Lab 2 to plot the graph.
What information does this graph tell you about Alphie's algorithm? Is it constant time, linear time, other polynomial time, or unreasonable time?