Solving the recurrence $T(n) = T(n/2) + cn \cdot \lg \lg n - 1$

Question

I'm trying to solve the recurrence

$$ \begin{eqnarray} T(n) & = & T\left( \frac{n}{2} \right) + cn\lg \lg n - 1\\ T(2) & = & 0 \end{eqnarray} $$ where $\lg n = \log_2 n$ to get the higher-order term exactly (in terms of $c$, presumably). I first tried to solve it iteratively, which got me the following expression that I have no clue how to evaluate:

$$ T(n) = c \sum_{i=1}^{(\lg n) - 1} \left[ \frac{n}{2^i} \lg((\lg n) - i) \right] - \lg n $$

If I make the substitution $n = 2^m$ and $S(m) = T(2^m)$, then I get a slightly nicer recurrence $$ \begin{eqnarray} S(m) & = & S(m - 1) + 2^m c\lg m - 1\\ S(m) & = & \sum_{i=1}^m (2^i \lg i) - (m-1) \end{eqnarray} $$

Wolfram Alpha gives me a crazy-looking solution to the summation, but it's not really what I'm looking for (WA solution here).

I'm pretty stuck at this point with this recurrence, after having also tried constructive induction on both $T(n)$ and $S(m)$ with no success, and at this point I've pretty much exhausted my toolbox. If anyone could offer any hints or general advice on solving this recurrence or similar reccurences, I would really appreciate the help. Thanks.

Answer 1

Let $n = 2^m$. We then have $$T(n) = T(n/2) + c n \log(\log(n))-1 \implies g(m) = g(m-1) + c \cdot 2^m \log(m \log(2))-1$$ where $g(m) = T(n)$. We hence get that (as you have already derived) $$g(m) = c \left(\sum_{k=1}^m \left(2^k \log(k) + 2^k \log(2) \right)\right)-m + g(0)$$ From here, we have $$\sum_{k=1}^m a(k)f(k) = A(m)f(m) - A(0)f(1) - \sum_{k=1}^{m-1} A(k) (f(k+1)-f(k))$$ where $A(k) = \sum_{j=1}^k a(j)$. In our case, choose $a(k) =2^k$ (i.e., $A(k) = 2^{k+1}-1$) and $f(k)=\log(k)$. We then get that \begin{align} \sum_{k=1}^m 2^k \log(k) & = (2^{m+1}-1)\log(m) - \sum_{k=1}^{m-1} \left(2^{k+1}-1\right)\log\left(1+\dfrac1k\right)\\ & = 2^{m+1} \log(m) - \underbrace{\sum_{k=1}^{m-1}2^k \log\left(\dfrac{k+1}k\right)}_{ = \mathcal{O}(2^m) \text{ since}\log\left(\frac{k+1}k\right)\leq \log(2)} \end{align} Hence, the leading term is $$c \cdot 2^{m+1} \log(m)$$