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?


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

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

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

  • $\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 '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$ Sep 17 '14 at 18:06
  • $\begingroup$ Ahh 0k, standard fact. Sorry. $\endgroup$ Sep 17 '14 at 18:51

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.