Master theorem - why the log factor?

Question

I think I finally managed to fully understand the master theorem but there's one thing left in the second clause (I'm following here: http://www.eecis.udel.edu/~saunders/courses/621/11s/notes/notes/Master-theorem.html)

$$ T(n) = O(n^dlog(n)), \\if\\ e = d $$

where does the $log(n)$ term come from? It seems like an "adjust value" since the phrase below recites

Paraphrase: The exponent of n is whichever dominates: the non recursive work (nd) or the total work at the deepest lever of recursion, alogb(n). But when these two are equal there is a log(n) factor.

So my question is: why was that log term put there?

Answer 1

Your lecture notes imply that $T(n)$ can be described by the formula $$n^d \sum_{i=1}^{\log_b n} \left( \frac{a}{b^d} \right)^i.$$ But consider this: $$\log(a/b^d) = \log a - d \log b =\left( \frac{\log a}{\log b} - d\right) \log b = ( e - d) \log b .$$ This is positive if $e > d$, negative if $e < d$, and zero if $e = d$. So if $e = d$, then $a/b^d = 1$, and the sum is just $log_b n$. That is, when $e = d$, $$n^d \sum_{i=1}^{\log_b n} \left( \frac{a}{b^d} \right)^i = n^d log_b n = \frac{1}{\log b} n^d \log n = O(n^d \log n).$$ So why doesn't this term show up when $e \ne d$? In the case where $e < d$, we can see that $\frac{a}{b^d} < 1$, and the sum asymptotically approaches a constant, so it does not figure in the $O()$ notation. On the other hand, if $e > d$, the sum grows exponentially, in fact it is $O(n^{e-d})$, and multiplied by $n^d$ this gives us $O(n^e)$.

In other words, the reason why the term of $\log n$ shows up only when $e = d$ is because that's the only case in which the ratio of terms in the sum is $1$, and therefore the only case in which the sum grows at the same rate as the number of terms. In the other cases it grows either much faster or much slower.

Answer 2

The recursion is $T(n) ≤ a⋅T(n/b) + c⋅n^d$.

Set $S(k)=a^{-k}⋅T(m⋅ b^k)$ where $n=m⋅ b^k$, $1/b\le m\le 1$ and thus $$k=\frac{\log(n)-\log(m)}{\log(b)}=\log_b(n)-\log_b(m), \quad-\log_b(m)\in[0,1].$$ The recursion then gets the reduced form \begin{align} S(k)&= a^{-k}⋅T(m⋅ b^k) \\ &\le a^{-k}⋅(a⋅T(m⋅b^{k-1}) + c⋅(m⋅b^k)^d \\ &=S(k-1)+c⋅m^d⋅(a^{-1}⋅b^d)^k \\ \implies\quad S(k)&\le S(0)+c⋅m^d⋅\sum_{j=1}^k(a^{-1}⋅b^d)^j \end{align} where $S(0)=T(m)$ is a bounded quanitity.

Now there are two cases to consider, either $b^d=a$ or not.

---

If not, then the sum is a geometric sum $$ \sum_{j=1}^k(a^{-1}⋅b^d)^j=b^d⋅\frac{(a^{-1}⋅b^d)^k-1}{b^d-a} $$ leading to \begin{align} T(n)=a^k⋅S(k)&\le a^k⋅T(m)+c⋅m^d⋅b^d⋅\frac{(b^k)^d-a^k}{b^d-a} \\ &=(n/m)^{\log_b(a)}⋅T(m)+c⋅(mb)^d⋅\frac{(n/m)^d-(n/m)^{\log_b(a)}}{b^d-a} \end{align} The dominant term of the expression depends on if $b^d>a$ or $b^d<a$, in the first case it is $n^d$, in the second $n^{\log_b(a)}$.

---

In the second case, $a=b^d$ or $d=\log_b(a)$, one gets $$ \sum_{j=1}^k(a^{-1}⋅b^d)^j=\sum_{j=1}^k1=k $$ and since $$ k=\log_b(n)-\log_b(m), $$ a term with factor $\log_b(n)$ appears. \begin{align} T(n)=a^k⋅S(k)&\le a^k⋅T(m)+c⋅m^d⋅a^k⋅k \\ &=(n/m)^{\log_b(a)}⋅T(m)+c⋅m^d⋅(n/m)^{\log_b(a)}⋅(\log_b(n)-\log_b(m)) \\ &=(n/m)^d⋅T(m)+c⋅n^d⋅(\log_b(n)-\log_b(m)) \end{align} $n^d\log_b(n)$ clearly dominates $n^d$.