5
$\begingroup$

Every time I solve these questions, I get stuck at the end where I need to find a closed form for the summation.

Here in this case, I have reached until this point: $$ \begin{align} T(n) &= T(n-2) + 1/\lg n \\ &= T(n-4)+ 1/\lg(n-2) + 1/\lg n \\ &= T(n-6) + 1/\lg(n-4) + 1/\lg(n-2) + 1/\lg n. \qquad (1) \end{align} $$ Assuming $T(1) = 1$, I put $n - 6 = 1$ and substituted into (1):

$$ T(6) = T(1) + 1/\lg3+ 1/\lg 5+ 1/\lg7.$$

Now at this point I am not able to find out $\sum_{i=1}^n 1/\lg(2i-1)$.

On similar grounds , I become blank for another recurrence relation $T(n) = T(n-1)+1/\lg n$, and my solution drills down up to here: $$T(n) = T(1)+ 1/\lg2 + 1/\lg3 + 1/\lg4 + \cdots.$$

How do I evaluate such sums?

$\endgroup$
  • $\begingroup$ Please read your question after posting it, and try to edit it so that it shows up correctly. Use LaTeX if possible. $\endgroup$ – Yuval Filmus Apr 24 '14 at 0:40
  • 2
    $\begingroup$ "summation has to be converted to a formula and that becomes the running time of the algorithm." -- no sum suddently becomes the running time. I don't know whether this weird choice of words is an actual misconception or just a language issue. $\endgroup$ – Raphael Apr 24 '14 at 6:28
  • 1
    $\begingroup$ I suggest you check out our reference question on solving recurrences; there are more methods available that involve less guessing. (Note that you also need an induction proof to verify your guess.) $\endgroup$ – Raphael Apr 24 '14 at 6:29
  • $\begingroup$ Further to Raphael's comment, a recurrence is just a way of specifying a function and that function could be used to measure literally anything, in just the same way that numbers can be used to measure anything. $\endgroup$ – David Richerby Apr 24 '14 at 9:01
6
$\begingroup$

The trick to evaluate these sums is integration. We have the following very useful inequality for a non-decreasing $f(i)$: $$ \int_0^n f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_1^{n+1} f(x) dx. $$ In your case, $f(i)$ is in fact non-increasing, and in that case we have $$ \int_1^{n+1} f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_0^n f(x) dx. $$ For example, we can estimate $$ \int_2^{n+1} \frac{dx}{\log x} \leq \sum_{i=2}^n f(i) \leq \int_1^n \frac{dx}{\log x}. $$ Unfortunately, the antiderivative of $1/\log x$ is not an elementary function, but is known as the logarithmic integral $li(x)$. Asymptotically, $li(x) \sim x/\log x$, and so we deduce $$ \sum_{i=2}^n \frac{1}{\lg i} = \Theta\left(\frac{n}{\log n}\right). $$ In this particular case, we can obtain these bounds directly. Since $1/\lg i \geq 1/\lg n$, we obtain a lower bound of $(n-1)/\lg n$. Conversely, for $i \geq \sqrt{n}$ we have $1/\lg i \leq 1/\lg \sqrt{n} = 2/\lg n$, and so $$ \sum_{i=2}^n \frac{1}{\lg i} \leq \sqrt{n} \lg 2 + n \frac{2}{\lg n} = O\left(\frac{n}{\lg n}\right). $$ If you want to obtain better estimates on such sums, the way to go is Euler–Maclaurin summation, which can be used to obtain an asymptotic series for $\log n!$, for example.

| cite | improve this answer | |
$\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.