Week 8 – Assignment 2, Midterm and Algorithms

It’s Sunday, and I’ve just submitted Assignment 2.  But, of course, the fun never ends. I have a quiz tomorrow on a new topic – Algorithm Analysis, and a midterm on Wednesday on Proofs.

Overall, I think I spent too much time on the second assignment checking and double-checking everything. There were a lot of idiosyncrasies between how the proofs were presented in the lecture and how they were shown in the tutorial. Not to mention the course notes package as well.  I’m sure they are all correct but some just make more sense to me than others.

There are some proof types that I will need work on before the midterm such as limit proofs, proofs about sequences and non-boolean proofs.  These are the most challenging since it is not always obvious whether a claim is true or false and a lot more time is spent pondering which is the correct way to go before you can put pencil to paper.

The thing with proofs, however, is that there is only one answer to each question, either true or false, despite the many ways of achieving it.  But, with algorithm analysis we seem to be taking something that should have only one answer, such as the worst case performance of an algorithm, and making it somewhat arbitrary by randomly overestimating or underestimating whenever we choose.  This begs the question how much is too much?  We can all grossly overestimate / underestimate our answer to simplify our lives but where do we draw the line between something that meaningfully represents the performance of an algorithm and something that is not even in the same ballpark.  I had this feeling at the end of lecture one day so I delved a little deeper only to find that things are not as random as they appear…

At the end of the W_IS in bigO(n²) (worst case insertion sort algorithm) lecture we had some function for bigO(n²) = 3n² + 6n + 2 and we wanted to simplify to some upper bound function in the form of cn².  The approach we took in class was just to add additional factors of n (this is the arbitrary part) to the remaining terms 6n and 2 so that we were left with cn² = 11n² with a breakpoint of n = 1.

So I was curious whether it was possible to do better in a less random fashion with relatively little work and with a minimal increase in the breakpoint of n = 1.  My approach was to solve for some incremental constant k such that kn² = 6n + 2.  The new kn² term would then be added to 3n² to obtain the upper bound cn².  As noted, there would be some trade off in the location of the breakpoint, as we will see.

To proceed I used the quadratic equation to solve for k, and if my math is correct we have the function B = (6 + (36 + 8k)^0.5) / (2k) where k is the incremental coefficient and B is the new breakpoint for the new upper bound function (3 + k)n².

So for bigO(n²) = 4n² we have a breakpoint of n = 7 (rounded up from 6.32).  In other words we can reduce the upper bound function by a factor of 2.75 (calculated by 11n²/4n²) if we accept a slightly higher breakpoint of n = 7.

Interestingly, if we substitute the incremental coefficient k = 8 (from the quick and dirty method used in class), the corresponding breakpoint is in fact n = 1, as if by magic!  But, of course, there is no magic here and the cold hard lesson is that we are actually doing the same thing but in different ways. The “quick and dirty method” used in class was to just pick the easiest possible constant c that satisfied the proof and then solve for the corresponding breakpoint B, while the method shown here, although less arbitrary, instead gives a general relationship between the breakpoint and the coefficient.

What a dull conclusion to such a long discussion…I think I better get back to studying for the midterm…