Week 6 : More Time Complexity, Unwinding and Master Theorem

We covered a lot of things in this week's lecture. But as I've made up the background knowledge that I was missing. I managed to catch up with the pace of the lecture (Again, thanks to Jason and Harry!).

First of all, we discussed more on Time Complexity on trying to calculate the upper bounds of recursive binary search. As we encountered trouble using the method we did to calculate lower bound, we applied another method, which to me is very similar to the former method, but just more tricky.

Then we learned to use Unwinding to analyze questions involving recursive definitions. Since I have done this a lot in my previous school (like analyzing Fibonacci Sequence), this is not hard to me. But I didn't quite catch up with how to prove the recurrence of binary search is non-decreasing. Then I read Lemma 3.6 in the textbook, it explains very clearly.

Later, we were introduced the Master Theorem, I found it really abstract and hard to understand. But since the professor didn't go into much detail, maybe this topic isn't that importan or we may go for the details later.

This week's lecture notes are as follows: