I am back in Toronto!

After 12 days, I am finally back to Toronto! Hopefully I will catch up the lectures and tutorials questions fast! From the lecture notes, seems that I have missed the materials based on Master Theorem, and some reviews in the past 2 weeks.

I applied the Master theorem to a recurrence for a running time I encountered 

T(n)=4T(n/2)+O(r)

r is independent of n. Case 1 of the Master theorem applies and tells us that T(n)=O(n2).

However, this hides a constant dependent on r in the big-oh notation: our recurrence has depth O(log2n) so at the final level we have O(4log2n)=O(n2) subproblems, each of which takes O(r)time to be handled. This means the actual running time is O(n2r) (or worse: this analysis only talks about the lowest level).

This is my actual recursion:

T(n)=r2T(n/r)+O(nr2)