1
$\begingroup$

$$\sum_{i=0}^{\log n - 1} \frac{1}{\log n - i} = \Theta(\log\log n)$$

Well, my maths skills aren't that good, so other than trying to insert $i=0,1,2,\ldots$ and summing it up didn't help me to get to $\log\log n\,.$ Any ideas?

Edit: maybe somehow taking the $log$ out, and then somehow discovering I have an harmonic series that goes down and its $logn$ too.. But I'm not sure how to implement this..

$\endgroup$
  • 1
    $\begingroup$ Start with the substitution $\log n=\mu$. It should be less confusing that way. $\endgroup$ – Simply Beautiful Art Sep 17 '16 at 15:09
  • $\begingroup$ Hint: Consider this sum as an approximation of the integral $\int\limits_{0}^{\log n -1}\frac{1}{\log n - x}dx$. $\endgroup$ – Mihail Poplavskyi Sep 17 '16 at 15:09
  • 2
    $\begingroup$ As said above take $\log n = \mu$ and reverse the summation ($i\to \mu - i$) and you are left with $\sum_{i=1}^{\mu}\frac{1}{i}$ the harmonic number (assuming $\log(n)$ here is really $\lfloor \log(n) \rfloor$) $\endgroup$ – Winther Sep 17 '16 at 15:12
  • 1
    $\begingroup$ @Winther That has division by $0$. You mean to start at $i=1$. $\endgroup$ – Simply Beautiful Art Sep 17 '16 at 15:13
1
$\begingroup$

Using the substitution $\log n=\mu$, we get

$$\sum_{i=0}^{\mu-1}\frac1{\mu-i}=\Theta(\log\mu)$$

If we approximate with an integral, we get

$$\sum_{i=0}^{\mu-1}\frac1{\mu-i}\approx\int_0^{\mu-1}\frac1{\mu-t}dt$$

And the rest should be quite clear.

$\endgroup$
  • $\begingroup$ Thank you. So I do get to a harmonic series to solve this. $\endgroup$ – Ilan Aizelman WS Sep 17 '16 at 15:14
1
$\begingroup$

Let we prove a preliminary lemma first.

Lemma $(1)$ $$H_m = \sum_{k=1}^{m}\frac{1}{k}=\Theta(\log m) $$

Proof. By the concavity of the logarithm function over $\mathbb{R}^+$ we have $$ \frac{1}{k}\leq \log\left(k+\frac{1}{2}\right)-\log\left(k-\frac{1}{2}\right) $$ for any $k\geq 1$, hence $H_m \leq \log(2m+1)$ is a consequence of a telescopic sum.
On the other hand, by the convexity of $\frac{1}{x}$ over $\mathbb{R}^+$ we have: $$ H_m-\frac{1}{2}-\frac{1}{2m}\geq \int_{1}^{m}\frac{dx}{x} $$ hence $H_m\geq \log(m)+\frac{1}{2}+\frac{1}{2m}$.


We may notice that $$ \sum_{0\leq i\leq \log(n)-1}\frac{1}{\log(n)-i}=\sum_{1\leq k\leq \log(n)}\frac{1}{k} = H_{\left\lfloor\log n\right\rfloor}\stackrel{(1)}{=}\Theta\left(\log\left\lfloor\log n\right\rfloor\right)=\color{red}{\Theta\left(\log\log n\right)}. $$

$\endgroup$

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.