Unit 5 Lab 4: Timing Experiments, Page 3

Classifying Algorithms

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

Blue button feedback:

For question #3, could you offer suggestions as to which algorithms might be good to revisit?

If it isn't already open, load the project U5L3-timer from the previous page, and experiment with time function on algorithms you've built (such as alphie way, betsy way, factorial, find in unsorted list, find in sorted list, and any others you have handy). What happens to the running 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.

Open this project, and use the block to build the following two blocks in Snap!. Then, determine which block's algorithm can be executed in a reasonable time, and which cannot.
The list of 2-digit numbers goes from 10 to 99. There's a math operations block that can give you powers of 10.

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

These 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 more than linear time.

Reasonable Time:

Some algorithms always 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 constant, linear, and quadratic functions, etc.), then the algorithm takes polynomial time and is reasonable.

Unreasonable Time:

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 (n) 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 exactly but give a reasonable approximation.

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 time function with large inputs to Alphie's way (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 is it unreasonable time?