2
$\begingroup$

There already are many questions and answers about the importance of the regularity condition in case 3 of the Master Theorem. My question is about when can we safely assume the regularity condition is satisfied when f is only provided as a $\Theta(g(n))$, which is actually what happens most of the time when we don't want to bother detailing the exact expression for $f$.

From my understanding, I believe that nothing can be assumed without additional information on f. In the example provided on wikipedia of $T(n) = T\left(\frac{n}{2}\right) + n(2 - \cos{n})$ we have $f(n) = \Theta(n)$ since $(2 - \cos{n}) \in [1, 3]$. Yet $f$ does not satisfy the regularity condition and we therefore cannot deduce that that $T(n) = \Theta(n)$.

Going down the definition of $f(n) = \Theta(g(n))$, we have $n_0 \geq 0$, $c_0 > 0$ and $c_1 > 0$ such that for every $n \geq n_0$ $c_0 g(n) \leq f(n) \leq c_1 g(n)$. Let's assume $g(n) = n^c$.

Given a Master Theorem instance of $T(n) = aT\left(\frac{n}{b}\right) + \Theta(n^c)$, we are in case 3 of the Master Theorem when we have $a < b^c$. Now to check the regularity condition we need to check that $a f\left(\frac{n}{b}\right) \leq kf(n)$ for some $k < 1$. We therefore have that for $n \geq n_0$ $$ \begin{aligned} af\left(\frac{n}{b}\right) &\leq a c_1 g\left(\frac{n}{b}\right)\\ &\leq a c_1 \frac{n^c}{b^c} \end{aligned} $$ and $$ \begin{aligned} kf(n) &\geq k c_0 g(n)\\ &\geq k c_0 n^c \end{aligned} $$ assuming $n > 0$, we therefore need that $$ \begin{aligned} k c_0 &\geq \frac{a c_1}{b^c}\\ k &\geq \frac{c_1}{c_0}\frac{a}{b^c}\\ \end{aligned} $$

In the Wikipedia example, we have $\frac{c_1}{c_0} = 3$ and $\frac{a}{b^c} = \frac{1}{2}$. We would therefore need that $k \geq \frac{3}{2}$ which contradicts $k < 1$.

Now when $f$ just comes out of a loop intrication without inner tests that would make the worst and best cases different, $f$ is a polynomial, and we just use its dominant power as a $\Theta$. I believe what saves us is that we can choose the $n_0$ in the Landau notation, and by increasing it we can have $\frac{c_1}{c_0} < \epsilon$ for any $\epsilon > 1$. And since $\frac{a}{b^c} < 1$, we can always find some $n_0$ such that for any $n \geq n_0$, the regularity condition is satisfied.

Is this sound ? Can we use the generalized Akra-Bazzi Theorem to just not bother ?

$\endgroup$
2
$\begingroup$

Suppose that $T(n) = aT(n/b) + \Theta(f(n))$. What this means is that $T(n) = aT(n/b) + g(n)$, where $g(n) = \Theta(f(n))$, say $c_{LB} f(n) \leq g(n) \leq c_{UB} f(n)$. Consider now the following two recurrences: $$ T_{LB}(n) = aT_{LB}(n/b) + c_{LB} f(n), \\ T_{UB}(n) = aT_{UB}(n/b) + c_{UB} f(n), $$ with the same initial conditions as the initial recurrence. You can show inductively that $T_{LB}(n) \leq T(n) \leq T_{UB}(n)$. Assuming that the function $f(n)$ does satisfy the regularity conditions, you can use the master theorem to solve the two auxiliary recurrences, and hence to deduce the solution to the original recurrence.

$\endgroup$
  • $\begingroup$ I see, thanks a lot. This means however that the Wikipedia example is not the best one could find, since in that case ignoring the regularity condition would have given the right answer anyway. This sheds light on your other answer about the regularity condition. $\endgroup$ – Vincent Nivoliers Mar 27 '18 at 11:42
  • $\begingroup$ Well, Wikipedia isn't perfect... $\endgroup$ – Yuval Filmus Mar 27 '18 at 11:49

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.