1
$\begingroup$

In the 4th edition of his Data Structures textbook, Weis gives a proof of part of the Master Theorem. This proof says "Let us ... ignore the constant factor in $\theta(N^k)$ ... I don't understand why it ignoring that constant is valid. (I know that the real Master Theorem is broader than the version presented in the text. I'm just having trouble understanding the argument presented in the text.)

Specifically, the relevant part of Theorem 10.6 on page 469 is

The solution to the equation $T(N) = aT(N/b) + \Theta(N^k)$ is $T(N) = O(N^{log_b} a)$ if $a > b^k$

The proof includes the phrase "ignore the constant factor in $\theta(N^k)$ ..." and then goes on to use a telescoping sum to get

$T(N) = T(b^m) = a^m \sum_{i=0}^m (\frac{b^k}{a})^i$

At this point, he argues that because $a > b^k$, then the sum is a geometric series with a ratio less than 1. However, if we don't ignore the constant in the $\Theta$ expression, isn't there a constant inside the summation that would affect whether the geometric series converges?

$\endgroup$
1
$\begingroup$

Suppose that your function is always in the range $cN^k$ to $CN^k$. Consider the three recurrences $$ s(N) = as(N/b) + cN^k, S(N) = aS(N/b) + CN^k, R(N) = aR(N/b) + N^k. $$ For appropriate initial conditions, $s(N) \leq T(N) \leq S(N)$ will hold, as a straightforward proof by induction would show. On the other hand, for appropriate initial conditions, $s(N) = cR(N)$ and $S(N) = CR(N)$, as another straightforward induction shows. This explains Weis's remark.

What it happening here? As you unroll the recursion, you add various terms which are $\Theta(N^k)$, for various values of $N$. The contribution of the big Theta to the final sum is at most a constant factor. Instead of $a^m \sum_{i=0}^m (\frac{b^k}{a})^i$, you get $\Theta\bigl(a^m \sum_{i=0}^m (\frac{b^k}{a})^i\bigr)$. Crucially, the additional constant factor is global and doesn't accumulate throughout the recursion.

As an example, consider the generic recurrence $s(N) = 2s(N-1) + f(N)$, with base case $s(0) = 0$. The solution is $$ s(N) = f(N) + 2f(N-1) + 4f(N-2) + \cdots + 2^{N-1} f(1). $$ If we multiply $f(N)$ by a constant factor, the solution of this recurrence will be multiplied by the same constant factor, while the constant $2$ stays the same.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Doh! I had made a dumb mistake and ended up with $\sum(\frac{cb^k}{a})^i$ instead of the correct $\sum c(\frac{b^k}{a})^i$ $\endgroup$ – Zack Nov 10 '19 at 23:15
  • $\begingroup$ Now, why does Weis divide through by $a^m$ instead of just allowing the original recurrence to telescope? Is it just because the resulting formula ($N^k \sum_{i=0}^{\log_b N} a^i$) doesn't lend itself to as tight of a result? $\endgroup$ – Zack Nov 10 '19 at 23:19
  • $\begingroup$ If you don’t like Weis’ style, I suggest picking a different textbook. $\endgroup$ – Yuval Filmus Nov 11 '19 at 3:45
  • $\begingroup$ I'm not saying I don't like it, I just don't understand this particular approach. I just want to make sure I'm not missing the bigger picture. $\endgroup$ – Zack Nov 11 '19 at 14:39
  • 1
    $\begingroup$ Weis wants to get a convergent series. It’s just a calculation device. There might be other ways of expressing the same idea. It’s a matter of style. $\endgroup$ – Yuval Filmus Nov 11 '19 at 14:42

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.