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.