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

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.

• How do you have as argument n/2, when n can be odd? Is it the whole part of n/2 or? – Alex Botev Apr 20 '13 at 3:03
• @Belov I'm allowed to assume n is "nice" as needed, so in this case that it is a power of 2 – xjtian Apr 20 '13 at 3:04
• Your T(1) doesn't make sense. lg (lg (1)) is not defined for any base. – Zen Apr 20 '13 at 3:08
• @Zen: Oops sorry! Base case is supposed to be T(2) – xjtian Apr 20 '13 at 3:09

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