0
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ Sep 16, 2014 at 23:59
  • $\begingroup$ You're right,to fix, how is this in latex? $\endgroup$ Sep 17, 2014 at 0:28
4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I like the simplicity and elegance of your argument, definitely. But, may be it's better a explicit proof for convince. $\endgroup$ Sep 17, 2014 at 17:08
  • 1
    $\begingroup$ @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$.) $\endgroup$ Sep 17, 2014 at 18:06
  • $\begingroup$ Ahh 0k, standard fact. Sorry. $\endgroup$ Sep 17, 2014 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.