Master Theorem: How to find the value of b in this recurrence relation

The master theorem is used with recurrences of the form T(n) = aT(n/b) + f(n) where a >=1 and b > 1, in which case the value of b can be easily seen from the recurrence, however I have a recurrence of the form

T(n) = T((n/4)+3) + f(n)

How do I get the value of b in this case?

This question Particularly Tricky Recurrence Relation (Master's Theorem) is the only thing I found that has a similar case with T(n/4 +1) but gives no detail about how the b was calculated.

You can't use the Master theorem on that function $T$.

However, as Raphael suggests, you could consider the related function

$$T'(n) = T'(n/4) + f(n),$$

use the Master theorem to find a solution for $T'$, and then check whether that's a valid solution for $T$ too. No guarantees that it will be, but you could check.

In other words, you could use the guess-and-check strategy to solve the recurrence for $T$, where your "guess" comes from solving $T'$ using the Master theorem. See also Solving or approximating recurrence relations for sequences of numbers for an explanation of guess-and-check (also called guess-and-prove).

One caveat is that guess-and-check will probably require an explicit solution to $T$, with specific constants. In other words, it's usually not enough to guess that $T(n) = O(g(n))$; you will typically need to guess a specific constant $c$ such that $T(n) \le c \cdot g(n)$, one that will enable the proof to go through.

StackExchange Computer Science Q#63981, answer score: 3