Problem Detail: 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:
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.
Asked By : Kyra Westwood
Answered By : Charles Wang
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11635
