CSC236 SLOG#4

I did the second midterm on last Thursday, the questions were not what I was expected. I talked to some friends in the morning session, they were getting questions on Upper and Lower bounds and proving closed form. But we were tested on the correctness and master-theorem. However, since I did my review for all materials, I am able to do most of the questions. 

The correctness proof was not challenging for the most part except the proof for termination. I know how to proof the termination, it is just that I do not know which format I should use since we never do proof of termination in lecture formally.

The second question suppose to be easier, but I made some mistake there. In part a, the "b" for master theorem suppose to be 2, but I wrote 3. My reasoning was that - "b" represents the number of pieces we divide the problem into, since we divide the problem into three parts (two parts of n//2 and one part of n%2), I figured "b" is three then. However, I talked to the professor later, who suggested the last part is not valid because it only recurses once. 

But then I was thinking should "b" depends on wether the parts are recursive? In wk7's lecture, we did an example on multiply lots of bits. It occurs to me, there are four parts recursing in the recombined equation, but we got "b" equals 2. I will great appreciate if anyone can answer me what "b" really is? I guess I will need to ask professor about this since no one really looks my slog lol.