Why can we ignore the constant factor in Weis's proof of the Master Theorem

Question

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?

Answer 1

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.