Timing Sum-thing's Up

Need a new title. --MF

We will now see an example where the runtime of an algorithm really does make a difference. Remember the game you played with young Gauss at the beginning of lab? We will implement the game in snap.

This was a link to /bjc-r/cur/programming/loops/sum-things-up.html, but that's not in the lab anymore, so what is the right thing? --MF

Earlier in the lab, you made a block that returned the sum of numbers between 1 and max. In the "Variables" palette, you will see two blocks:

GH Feedback 7/21/15: The two block images shown on the page differ from the blocks in the Snap! project for this lab (in the lab, they don't have the input spaces or the word "in"). They also differ from the descriptions lower on the page, which describe "add all numbers between 1 and max" instead of "add all numbers in list"
add all numbers in list

The first block sums up the numbers in the numbers list the normal, "non-Gauss" way: walking through the list and adding the numbers one by one. The second block sums up the numbers the "Gauss" way: using the formula $$(N + 1) \times (N รท 2)$$ where, in this case, N is the same as max. (How did we get this formula?)

  1. Complete the bodies of these blocks.
  2. Once you are done, drag the first block (the "non-Gauss" block) onto the stage and place it immediately after the add all numbers between 1 and max block.
  3. Then, move the reset timer block after the add all numbers between 1 and max block, since we only need to time how long the "non-Gauss" block takes to sum the numbers in the numbers list.
  4. Now, run the script with max set to 10. Again, run it a few times to get an idea of the average time the computer takes to sum the numbers up.
  5. Repeat the experiment with max set to:
    • 20
    • 40
    • 100
    • 1000
  6. Talk with Your PartnerBased on your observations, what kind of runtime does the "non-Gauss" block have: constant, linear, or neither? Why do you think this is the case?
  7. Replace the "non-Gauss" block with the "Gauss" block and run the script once more with max set to 10. Again, run it a few times to get an idea of the average time the computer takes to sum the numbers up.
  8. Repeat the experiment with max set to:
    • 20
    • 40
    • 100
    • 1000
    9. This could easily be a quiz question. --MF
  9. Talk with Your Partner Based on your observations, what kind of runtime does the "Gauss" block have: constant, linear, or neither? Why do you think this is the case?