SLOG #8

    This week we focused on calculating the upper bound of the worst case scenario for a function and of the other polynomials. The material expanded to proofs involving big-Oh of a polynomial with multiple (3) terms as the upper bound. So first we looked to simplify the original function (also a polynomial) down to one term, by raising every term contained in that function to the highest degree. We then looked to simplify the upper bound by finding new polynomials that are both smaller and contain fewer terms than the original. Eventually we were able to have the upper bound be represented by only one term, and the rest of the proof was done automatically.
    The tutorial questions from this week caused some confusion for me, because we used a formula to sum up the numbers in a sequence when counting the steps of a program, but professor Heap did not used that formula on a similar question during lecture. The example in lecture appeared as follows:
def IS(A):
    i = 1
    while i < len(A):
        t = A[i]
        j = i
        while j < 0 and A[j - 1] > t:
            A[j] = A[j - 1]
            j = j -1
        A[j] = t
        i = i + 1
    When calculating the number of times the inner loop is executed, professor Heap wrote (n - 1)(i), n being the length of the input list, and later simplified it to (n)(n). But in the tutorial, we had to find exactly how many times, for each iteration of the outer loop, the inner loop is executed. For example, the inner loop executed once when i is 1, and five times when i is 5 (that is, if i can go up to and including 5). I was quite confused by these two different methods of calculation, because I thought they served the same purpose. However, it turns out that the example in lecture was an overestimate, and the question in tutorial asks for a very precise answer. So when doing proofs of big-Oh of some program, we can quite lazily (perhaps irresponsibly?) add a few more loops to the execution of the original program as long as the result does not exceed the growth rate of the same order, for example, x^2. However, when we are asked to computer the number of steps performed by an algorithm in the worst-case, we have to make sure that the number or expression we produce actually points to the number of steps for the worst case, not some vague overestimation.