# How to simplify the sum over 1/i?

With the recurrence relation: $$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$$

The "sum for all levels" in the recurrence tree is: $$\sum_{i=0}^{\log n -1} \frac{n}{\log n - i} = \sum_{i=1}^{\log n} \frac{n}{i} = n \sum_{i=1}^{\log n} \frac{1}{i}$$

Inside the analysis of the recurrence, $\sum 1/i$ appears and then bounded by $\Theta(\log\log n)$. Why is this?

$\sum_{i=1}^k\frac{1}{i}$ is the $k$th harmonic number, which is $\Theta(\log k)$.

• I like the simplicity and elegance of your argument, definitely. But, may be it's better a explicit proof for convince. – jonaprieto Sep 17 '14 at 17:08
• @d555 It's a standard fact and, hey, you've already included most of the proof in your answer. ($\sum_{x=2}^k\frac1x<\int_1^{k+1}\frac1x\,\mathrm{d}x<\sum_{x=1}^k\frac1x$, the integral is equal to $\log(k+1)$ so $H_k-1<\log(k+1)<H_k$, so $\log(k+1)<H_k<\log(k+1)+1$.) – David Richerby Sep 17 '14 at 18:06
• Ahh 0k, standard fact. Sorry. – jonaprieto Sep 17 '14 at 18:51

If you consider the last term in general, $\sum_{[1\leq i \leq \log n -1]} \frac{1}{i}$ as $$\sum_{[1\leq i\leq k]} \frac{1}{i}$$ In this way, you can establish a bound using a integral generalization for this sum: $$\sum_{[1\leq i\leq k]} \frac{1}{i} \leq \int_{0}^{k} \frac{1}{x} dx = \ln (x)|_{0}^{k}= \ln(k) - \ln(1) = \ln(k)$$ But, in your problem, as we know, $k = \log n - 1$, so for above:

$$\sum_{[0\leq i \leq \log n -1]} \frac{1}{i} \leq \ln (\log n - 1)\leq \ln \log n$$

For that, $$\sum_{[0\leq i \leq \log n -1]} \frac{1}{i} = O(\ln\log n)$$

But, you can exhibit a constants to achieve, $\Theta(\log\log n)$.

• Up to constants you may choose logarithm base 2. But when computing the primitive of $x^{-1}$ then the exact answer is $\ln(x)$, the natural logarithm, base $e$. – Hendrik Jan Sep 16 '14 at 23:59
• You're right,to fix, how is this in latex? – jonaprieto Sep 17 '14 at 0:28