Divide et impera for matrices rotating

Question

I have tried to solve the 2nd problem b and d subproblems from this exercise: http://courses.engr.illinois.edu/cs473/sp2010/homework/hw1.pdf

I solved the b to the following way:

My first question is that: Is my solution correct for the problem 2/b? My second question is: What I supposed to do the in problem 2/d? This a bit strange for me.

Thanks for your time and help.

Answer 1

From reading the second paragraph of the problem, it seems to me that your answer is not correct for part 2b. My reading was that a 2^n rotate would take 5 blits of 2^(n-1). If this is correct, then your equation should be

B(2^n) = 5 * B(2^(n-1)) = 25 * B(2^(n-2)) = ... = 5^n * B(1)

Where B(x) is the number of blits for x. (Sorry for not knowing how to do fancy equations.)

For 2d, I read it as saying what is the time complexity of B(2^n). Give it a try and let's see what comes out of it.

Let me know what you think.