3
$\begingroup$

Consider a recurrence of the form

$T(n) = a T(n/b) + f(n)$

Master theorem's regularity condition excludes some cases (for example, when $f(n)$ is oscillating).

Suppose, however, that $f(n)$ is always less than or equal to a function $g(n)$ that does not violate the regularity condition, so that the master theorem is applicable if $g(n)$ is used instead of $f(n)$. Consider then the following recurrence:

$T'(n) = a T'(n/b) + g(n)$

and assume that the master theorem gives the solution $T'(n)=\Theta(g(n))$.

My doubt is this: can I then safely conclude that $T(n)=O(g(n))$?

In other words, can I be sure that the solution of a recurrence with a term replaced by its upper bound is an upper bound of the solution of the original occurrence? After all, the recurrence establishes a relationship between $T(n)$ and $T(n/b)$ but says nothing about what happens between $n/b$ and $n$ (and $f(n)$ here is oscillating...).

$\endgroup$
  • 1
    $\begingroup$ Yes, it is possible, since the solution of one recurrence upper bounds the solution of the other. $\endgroup$ – Yuval Filmus Jul 13 '18 at 12:09
  • $\begingroup$ Ok, but how can you be sure of that? I guess that you can claim that if you also know that T' is an upper bound for T (but you only know that g(n) is an upper bound for f(n)). I would then try to prove by induction that T'(n)>=T(n) for every n. Am I on the right track? $\endgroup$ – Maiaux Jul 13 '18 at 12:16
  • 1
    $\begingroup$ Right, it's a simple proof by induction. $\endgroup$ – Yuval Filmus Jul 13 '18 at 12:26
  • $\begingroup$ If T'(i)>=T(i) for all i between 1 and n (inductive hypothesis) then I think it's easy to show (inductive step) that T'(n+1)>=T(n+1) by expanding the recurrences, since all terms in the first one are greater than or equal to the terms in the second one. But what about the base case (initial condition)? How to show that T'(1) >= T(1) ? $\endgroup$ – Maiaux Jul 13 '18 at 17:03
2
$\begingroup$

Yes, you can. You are defining the recurrence $T'$, so define $T'(1) = T(1)$. Then, since $g(n)$ satisfies the regularity conditions, the Master theorem tells you that $T'(n) = \Theta(g(n))$. Note that the Master theorem doesn't depend on the choice of $T'(1)$; it is a constant, and you get the same asymptotic bound for $T'(n)$ regardless of which constant you choose.

Now, you can prove by induction that $T(n) \le T'(n)$ holds for all $n$. This is a simple induction. The base case holds because you defined $T'$ that way. The inductive step holds because $f(n) \le g(n)$ for all $n$.

Once you've proven that $T(n) \le T'(n)$ for all $n$, you are entitled to conclude that $T(n) = O(T'(n))$ and thus $T(n) = O(g(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.