After a month of getting stuck in 4.3-6. I passed the 1 month period which I vowed to not look up a solution if I couldn't solve a problem. Eventually, I found the solution on the web and it was not a short solution and it takes some time to understand.
What was the issue then? As it turns out, it's because I use a wrong form of guess. So no matter what I do, I still couldn't find the answer.
Another thing I learn is that one should always try to understand how the base case works first. The implicit question asked in every questions in Section 4.3 and 4.4 is that "What the initial condition is?" If I had thought through, may be I could resolve the issue.
Oh well, at least I am unstuck. This problem should be studied and it deserved a write-up.
Please can you post the link to the solution, i'm stuck and i can't find it on the web.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteWatch the second video lecture from MIT:
ReplyDeletehttp://www.catonmat.net/blog/mit-introduction-to-algorithms-part-one/
Use the idea of residual and the same reasoning line used by the professor on the class example: T(n) = 4T(n/2) + n
and you will get the right answer.
After trying, if you need help, mail me at leandro.luque@gmail.com