Bounds

I was feeling confident after the evening test. I felt like I understood the questions immediately and knew what methods I needed to avail of to solve them (of course, I have yet to find out whether my intuition was correct, the marks haven't been posted yet). I foolishly stumbled on the base case for the third question and by the time I knew what I had done wrong, it was too late to fix it, but I feel that overall it went well.

It would only be appropriate, then, that my heart would sink immediately as the professor started lecturing - lower bounds were definitely my downfall in CSC165. The reasoning for calculating lower bounds that my TA introduced in that course was completely different from the one that I later learned our professor was expecting from us (once the answers for the exercises were released). The answers involved capital-sigma notation, which I now have some facility with in this course when it comes to the mathematical proofs we did, but I still don't completely understand when to use it when applied to loops.

Now, looking at the binary search slides from last Thursdays lecture, I can honestly say I have no idea what is going on. I like how it says "trouble!" under the first upper bound slide, as if I hadn't been panicking for the entire lecture before that slide. I understand that we're supposed to be counting each step, and then repeating it for whatever number n times the loop goes around, and we incorporate recursion via the 'unwinding' method (which I understand in a general sense), but once I get to the later slides with all the gnarly mathematical proof work, I'm completely lost. I'll have to go to office hours tomorrow because I don't know how to do the tutorial hand-out at all.