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

Question

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.

Answer 1

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.

Answer 2

I don't think you can use master's theorem. However, there is a much more general version of that called Akra-Bazzi Method which can be used to solve this problem

Answer 3

What you can do is to use the master theorem to get lower and upper bounds separately, and then try to use other methods to prove a tight bound.

So, on one hand we have

$T(n) \leq T(n/3) + f(n)$

this is true because $T$ is an increasing function and $n/4 + 3 \leq n/3$ for $n$ big enough.

You will be using the master theorem with the following recurrence:

$T'(n) = T'(n/3) + f(n)$

and getting $T'(n) \in \Theta(g(n))$ for some $g$. So you will conclude $T(n) \in O(g(n))$

For the lower bound use $T(n) \geq T(n/4) + f(n)$.