Master's theorem is shown below,

enter image description here

The recursive function to be solved is shown below,

enter image description here

I understand that a refers to the number of recursive calls in this function (3 in this case). b refers to what the input size is being divided by in each recursive call. Which I believe should be 4. d refers to the overhead of each recursive call, which should be 1.

So we have:

a = 3
b = 4...?
d = 1

The problem is, b apparently doesn't equal 4.

Now the actual answer shows that the answer is:

enter image description here

Which seems incorrect, since given the Master's Theorem, I don't see how n is being subtracted by a constant.

Thank you for your help.


Since n refers to "the length in bits of x", you should translate n with the binary log of x, and (n-2) with the binary log of x/4.

Hope it helps.

| cite | improve this answer | |
  • $\begingroup$ Great! Can't believe I missed that! $\endgroup$ – Kyra Westwood Apr 28 '13 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.