World's most popular travel blog for travel bloggers.

# Understanding Master Method's Case 2

, ,
Problem Detail:

Whats the intuition behind multiplying the factor $\log n$

Master Method Case 2 (CLRS Section 4.5)

If $f(n) = \theta(n^{\log_b a})$, then $T(n)= \theta(n^{\log_b a} \log n)$

In generalized form sometime it can be written as

If $f(n) = \theta(n^{\log_b a} log^k n)$ with $k = 0$, then $T(n) = \theta(n^{\log_b a} \log^{k+1} n)$

###### Answered By : Yuval Filmus

Suppose that $T(n) = aT(n/b) + n^{\log_b a}$ and $T(1) = 1$. Now consider some $n$ which is a power of $b$, say $n = b^k$. The formula gives \begin{align*} T(n) &= aT(n/b) + n^{\log_b a} \\ &= a^2T(n/b^2) + a(n/b)^{\log_b a} + n^{\log_b a} \\ &= a^3T(n/b^3) + a^2(n/b^2)^{\log_b a} + a(n/b)^{\log_b a} + n^{\log_b a} \\ &= \cdots \\ &= a^kT(n/b^k) + a^{k-1}(n/b^{k-1})^{\log_b a} + \cdots + n^{\log_b a} \\ &= a^k + a^{k-1}(n/b^{k-1})^{\log_b a} + \cdots + n^{\log_b a} \\ &= a^k(n/b^k)^{\log_b a} + a^{k-1}(n/b^{k-1})^{\log_b a} + \cdots + n^{\log_b a}. \end{align*} There are $k+1 = \log_b n + 1$ terms in the final formula. Miraculously, all of them are equal to $n^{\log_b a}$! (Work that out on your own.)