# Particularly Tricky Recurrence Relation (Master's Theorem)

Master's theorem is shown below,

The recursive function to be solved is shown below,

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:

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.

## migrated from stackoverflow.comApr 28 '13 at 19:13

This question came from our site for professional and enthusiast programmers.

## 1 Answer

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.

• Great! Can't believe I missed that! – Kyra Westwood Apr 28 '13 at 11:00