3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ See our reference question for other methods you can apply. $\endgroup$ – Raphael Sep 28 '16 at 6:11
  • 1
    $\begingroup$ You can also investigate how T and $T'$ given by $T'(n) = T'(n/4) + f(n)$ differ. $\endgroup$ – Raphael Sep 28 '16 at 6:12
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Sep 28 '16 at 6:12
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This question link has T(x/4+1) and looks like the master theorem was used but no details were given. So I suspect that it indeed might be used in this case. I would love to ask how they got b in that post but I don't have enough reputation to comment on that post so I was hoping someone here knows how. I edited my question to make it clear that I am specifically interested in how to use the master theorem. $\endgroup$ – EvaD Sep 28 '16 at 2:29
  • $\begingroup$ @EvaD No, it doesn't. There is f(x/4 - 1) but that's in the algorithm, not in the running-time recurrence. Is that the mistake you are making? $\endgroup$ – Raphael Sep 28 '16 at 6:13
  • $\begingroup$ @EvaD, that question was a bit sloppy; the Master theorem doesn't seem to apply to that question (they might have used it, but strictly speaking, its use doesn't seem to be justified). So I think iLoveCamelCase's answer is the one that is ultimately correct. $\endgroup$ – D.W. Sep 28 '16 at 17:34
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.