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.

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

  • $\begingroup$ Ah, summation by parts was the critical step I was missing! I thought the S(m) summation looked familiar when I wrote it down, but just couldn't put my finger on exactly why. Should have flipped through more of my notes. Thanks! $\endgroup$ – xjtian Apr 20 '13 at 3:15

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.