3
$\begingroup$

I am struggling to solve this equation: $T(n)=2T(n/2) + n\log(\log n).$ I concluded that the Master Theorem does not apply in this situation so I tried to successively substitute the terms in order to solve this equation but cannot proceed. Could somebody tell me what would be the best way to solve this?

Thanks.

  • 0
    Please state the problem in the body of your question, not just in the title.2012-06-08

2 Answers 2

2

We are given that $T(n) = 2 T(n/2) + n \log_2(\log_2(n))$ (Note that if we take $\log$ to the base $2$ or to the base $e$, the only difference is in the coefficient of the leading order term).

Let $n = 2^k$. Call $T(n) = g(k)$. Then we have \begin{align} g(k) & = 2g(k-1) + 2^k \log_2(k)\\ & = 2 (2g(k-2) + 2^{k-1} \log_2(k-1)) + 2^k \log_2(k)\\ & = 4 g(k-2) + 2^k \log_2(k-1) + 2^k \log_2(k)\\ & = 4 (2g(k-3) + 2^{k-2} \log_2(k-2))+ 2^k \log_2(k-1) + 2^k \log_2(k)\\ & = 8 g(k-3) + 2^k \log_2(k-2) + 2^k \log_2(k-1) + 2^k \log_2(k) \end{align} Hence, in general, \begin{align} g(k) & = 2^k g(0) + 2^k \left( \log_2(1) + \log_2(2) + \log_2(3) + \cdots + \log_2(k)\right)\\ & = 2^k g(0) + 2^k \log_2(k!) \end{align} Now from Stirling's formula, we have that $k! \sim C \sqrt{k} \left(\dfrac{k}{e} \right)^k$ Hence, $\log_2(k!) = k \log_2(k) - k \log_2(e) + \dfrac12 \log_2(k) + \mathcal{O}(1)$ \begin{align} g(k)& = 2^k g(0) + 2^k \left( k \log_2(k) -k \log_2(e) + \dfrac12 \log_2(k) + \mathcal{O}(1) \right)\\ & = 2^k k \log_2(k) - k2^k \log_2(e) + 2^{k-1} \log_2(k) + \mathcal{O} \left(2^k \right) \end{align} Now plug in $k = \log_2(n)$, to get \begin{align} T(n) & = n \log_2(n) \log_2(\log_2 n) - n \log_2(n) \log_2(e) + \dfrac{n}2 \log_2(\log_2 n) + \mathcal{O}(n) \end{align}

1

Here's a 'straightforward' (i.e. non-rigorous) partial answer that may help you build your intuition. Assume all logs are base 2. By expanding $m$ times you can find that

$T(n) = 2^m T(n/2^m) + n\sum_{j=0}^{m-1} \log\log(n/2^j)$

so if we let $n=2^k$ and $m=k$, then

$T(n) = n T(1) + n\sum_{j=0}^{\log n - 1} \log\log (n/2^j)$

This gives you the easy bound

$\begin{align} T(n) & < n T(1) + n\sum_{j=0}^{\log n-1} \log \log n \\ & < nT(1) + n\log n \log\log n \end{align}$

and so you definitely have $T(n)=O(n\log n \log \log n)$.

By being more careful when bounding the sum (e.g. see Marvis's answer) you will be able to prove that $T(n)=\Theta(n\log n\log \log n)$ as well.