1
$\begingroup$

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)$

$\endgroup$
  • $\begingroup$ This works for all real $k$, positive or negative. $\endgroup$ – Yuval Filmus Sep 13 '15 at 13:52
  • 1
    $\begingroup$ For the intuition, have you tried looking at the proof? $\endgroup$ – Yuval Filmus Sep 13 '15 at 13:53
0
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Thanks didn't look CLRS. Proof pretty straight forward. $\endgroup$ – Atinesh Sep 14 '15 at 17:34

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.