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$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I like the simplicity and elegance of your argument, definitely. But, may be it's better a explicit proof for convince. $\endgroup$ – jonaprieto Sep 17 '14 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$ – David Richerby Sep 17 '14 at 18:06
  • $\begingroup$ Ahh 0k, standard fact. Sorry. $\endgroup$ – jonaprieto Sep 17 '14 at 18:51
4
$\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$
  • $\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$ – Hendrik Jan Sep 16 '14 at 23:59
  • $\begingroup$ You're right,to fix, how is this in latex? $\endgroup$ – jonaprieto Sep 17 '14 at 0:28

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.