SLOG #7

    This week we covered the calculations and proofs for the upper boundary and the lower boundary of the worst case scenario for an insertion sort algorithm. Both proofs were fairly easy to follow after accepting the fact that we can find the value of a variable after it has already been introduced, and fill that value in for the assignment statement at or near the beginning of the proof. However, I imagine writing similar proofs on different algorithms to be far more difficult than just following the professor's steps, because counting the number of possible repetitions for each line can get tedious very quickly with nested while loops and boolean operators (not, and, or) inside their loop conditions.     One question I have in mind is the precision to which we calculate the boundaries. When Professor Heap did the big-Oh proof, he arrived at a step WIS(A) ≤ 1 + 5(n - 1) + 1 + (n - 1) * (3i  + 1), then he said, since n > n - 1, then it's fine to write the next line as ≤ 1 + 5n + 1 + n(3i + 1). I find this somewhat unfitting in a rigorous process such as computing the upper boundary for the steps a program takes to execute. When we arrived at the polynomial an^2 + bn + c, every term was changed to have variables raised to the highest degree, so the result was  an^2 + bn^2 + cn^2. Then, every term in that polynomial can be considered equally as important, thus when we see n - 1 as n, we may miss the actual number of steps for the worst case scenario by quite a lot. 
    For this particular example, if I wanted to expand 1 + 5(n - 1) + 1 + (n - 1) * (3i  + 1), I could write i as (n - 1), since i starts from 1 and goes up to n -1 (n being the length of the list). Then I would have
WIS(A) ≤ 2 + 5(n - 1) + (n - 1)*(3(n - 1) + 1)
WIS(A) ≤ 2 + 5n - 5 + (n - 1)*(3n -2)
WIS(A) ≤ 2 + 5n - 5 + 3n^2 -5n + 2
WIS(A) ≤ 3n^2 - 1
WIS(A) ≤ 3n^2
    So the upper boundary is actually 3n^2 instead of 11n^2, less than 30% of what was originally estimated.
    Now, as I was doing the above expansions I realized we only needed to prove an existential statement, so we need not to be so rigorous after all. Go me.
    Also I'm lost as to what the breaking point (B) of WIS(A) ≤ 3n^2 is, perhaps it's zero? In retrospect, maybe I shouldn't have expanded that polynomial.