Running-time analysis: when to use summations? (A1 Q3)

There was a lot of confusion in class as to when to use summations, and which method to use in the assignment.

We discuss two methods to analyze worst-case running time.

Problem: A loop has 10 iterations (i). The running-time of each loop is equal to i. eg. First loop costs 1, second loop costs 2, last loop costs 10.

1. Summations
   The examples from tutorial 4 and this lecture supplement both used summations. Specifically, they used a formula to calculate the sum of the first n-1 numbers.

   Solution: "The sum of the first 10 numbers is 1+2+3+4+5+6+7+8+9+10  = 55."

   pros: more accurate than the method below
   cons: much more involved, need to know some formulas for summations, and easier to make mistakes because of the sheer amount of math (expanding, simplifying, etc.)

2. Assume every iteration of a loop will run, at worst, as slow as the slowest iteration.
   We used this in tutorial 5, to simplify the proof in tutorial 4. We followed this example on the course website (third example).

   Solution: "The slowest iteration takes 10 units of time. Every loop costs at most 10. The result is at most 10 iterations x 10 cost = 100."

   pros: much simpler and quicker, no summation formulas to remember
   cons: less accurate

So which one should you pick? If you are trying to be as accurate as possible, then you should use summations. However, when we compare algorithms, we usually focus on their asmpytotic growth rates, rather than the constants. In the above examples, summations gave us a result of 55, whereas using a worst-case assumption gave us 100. It's obvious which one is more accurate, but both are simply constants, therefore their growth rates are equal. Both methods are valid for the assignment, and assuming you didn't make any mistakes, your result for Q4 will be the same.