For this section, we will be using this timing script. It is very similar to the script you constructed earlier, but it also has the beginnings of a few blocks that we will be filling in. The first block that we will fill in is already on stage:
This block should fill the input list with all of the numbers from start to end. If working correctly, the version used on stage should generate all of the numbers from 1 to max, where max is a number that we will change when running timing experiments, and should add them to the numbers list.
Discuss an algorithm that you can use to fill the input list with all of the numbers from start to end.
max set to 10. Run it a few times to get an idea of the average time the computer takes to generate this list (to the nearest tenth of a second—you don't need to be exact).max set to:
You may have noticed that if you increased max by a factor of two, then the computer took approximately twice as much time to fill the numbers list. Similarly, if you increased max by a factor of ten, then the computer took approximately ten times as much time; if you increased max by a factor of 100, then the computer ran approximately 100 times longer. In general, as we scale the size of the input by a certain amount, we also scale the running time by the same amount. We call these algorithms linear-time algorithms, because if we were to plot the runtime of one such algorithm against the size of its input, we would get a line.
Why is the algorithm above a linear-time algorithm? When max was set to 20, we had to add 20 numbers to the numbers list; when max was set to 40, we had to add 40 numbers to the number list. In other words, as we scaled max, we also scaled how many numbers we had to add to the numbers list by the same amount. Linear-time algorithms are also much sought-after in computer science, and for many problems, they are the fastest algorithms you can find.