Yay! A week free of intense course work! Anyways, there's nothing special about this week. There's more unwinding and more merge sort, which I've been studying since grade 11. They weren't particularly hard to understand. However, the master theorem of divide and conquer was confusing. Although it may seem like proving it is just another time complexity problem, it is just strange to prove the time complexity of something that's not a function.
-Problem set 3-
We finally get to do a problem on unwinding. The function was a bit tricky to unwind because it involved the use of geometric series, which I didn't realize until someone told me. As long as you get the idea of using geometric series to unwind, proving it is very straightforward. We need to use our all time favorite - induction.
No comments:
Post a Comment