Take the 2-minute tour ×

I was solving recurrence relation of Introduction to Algorithms by CLRS, 3rd. edition. Problem 4-3 (i)
$$ T(n) = T(n-2) + \frac{1}{lg \; n} $$

I tried few ways, like expending with iteration method. With that i came up with the following equations - For even -

$$ T(n) = T(0) + \frac{1}{lg \; n} + \frac{1}{lg \; (n-2)} + \frac{1}{lg \; (n-4)} + ... + \frac{1}{lg \; 6} + \frac{1}{lg \; 4} + \frac{1}{lg \; 2} $$

For odd

$$ T(n) = T(1) + \frac{1}{lg \; n} + \frac{1}{lg \; (n-2)} + \frac{1}{lg \; (n-4)} + ... + \frac{1}{lg \; 7} + \frac{1}{lg \; 5} + \frac{1}{lg \; 3} $$

We can assume $T(1)=1$ and $T(0) = 1$. So to solve it I need to be able to sum up

$$ \sum ^{n}_{i=2} \frac{1}{lg\;i} $$

Some help will be greatly appreciated. Thanks.

share|improve this question

closed as off topic by Sjoerd C. de Vries, rcollyer, Mr.Wizard Oct 4 '12 at 12:10


Are you sure you have posted this at the correct site? Math.stackexchange.com is about mathematicS whereas Mathematica.stackexchange.com is about the computer language and environment MathematicA. –  Sjoerd C. de Vries Oct 1 '12 at 20:44
I am afraid you are right. Actually this is my first post in a stackoverflow like site. I apologise for any inconvenience. However, this opened the infinite posibilites of MathematicA. With whuber's analysis I now have idea how MathematicA could help me on analysing recursive algorithm's time complexity. Thanks for your great answers. –  fahad.shaon Oct 3 '12 at 15:18
No worries. In light of whuber's excellent answer, I suggest leaving this question here on this site as it is a good example of how Mathematica can aid the exploration of solutions. In future, if you have a math question, you can ask it at Mathematics :) –  The Toad Oct 3 '12 at 16:27

2 Answers 2

Sums can often be closely approximated by integrals.

Viewing $1/lg(i)$ as the area of a rectangle of height $1/lg(i)$ and width $1$ centered at $i$, we have

$$\sum_{i=2}^n \frac{1}{lg(i)} \approx \int_{i=3/2}^{n+1/2} \frac{dx}{lg(x)}.$$

Mathematica expressions for the two sides are

f[n_] := Sum[1/Log[2, i], {i, 2, n}];
g[n_] := Evaluate @ Integrate[1/Log[2, x], {x, 2 - 1/2, n + 1/2}];

A plot shows show close the two areas really are:

With[{n = 10},
 Show[Plot[{g[x], g[Round[x]]}, {x, 3/2, n+1/2}, 
   PlotRange -> {Full, {0, Automatic}}, AxesOrigin -> {0, 0}, Filling -> 0],  
  DiscretePlot[f[i], {i, 2, n}, PlotStyle -> PointSize[0.015], 
   Filling -> 0, FillingStyle -> Directive[Black, Thick]]]]


We can ask what the integral is in closed form:

? g

Definition of g

It is a "LogIntegral". What you're interested in for analysis of algorithms is the aymptotic behavior as the argument grows large. Obtain this with a series expansion:

a = Simplify[Series[LogIntegral[j], {j, Infinity, 1}]]


It's a bit of a mess, but a moment's inspection will reveal that the first half can be ignored--it's just messing around with the possibility that $j$ is complex--and the $i$'s cancel in the second half. So we can invoke Simplify on that second half, obtaining

(j (24 + 6 Log[j] + 2 Log[j]^2 + Log[j]^3 + Log[j]^4))/Log[j]^5

As $j$ grows large, so do all these terms. The two fastest-growing are the $j$ in the numerator and the $\log(j)^5$ in the denominator. Focusing on them, we can determine they are the only ones that matter asymptotically:

Limit[a / ( j/Log[j]), j -> Infinity]


As a double check, let's plot how close the evident approximation $f(n) \approx \frac{n}{lg(n)}$ really is as $n$ grows large. The horizontal axis here is logarithmic:

ListPlot[Table[f[n] / (n / Log[2, n]), {n, 10^Range[5]}], 
 Joined -> True, PlotStyle -> Thick, AxesOrigin -> {0, 1}]

List plot

OK, it will take a while before $f(n)$ is very closely approximated by $\frac{n}{lg(n)}$, but up to a small constant multiple it really looks like $T(n) = O(\frac{n}{lg(n)})$.

share|improve this answer
RSolve[{ t[n + 2] - t[n] - 1/Log[n] == 0, t[0] == 1, t[1] == 1}, t[n], n]

enter image description here

Let's define T :

T[n_Integer /; n >= 0] = t[n] /. First[%]

Mathematica cannot further simplify the result, e.g. :

T[#] & /@ Range[6, 10]

enter image description here

unless one looks for numerical results :

T[#] & /@ Range[6, 10] // N
{3.16404, 2.53157, 3.72215, 3.04547, 4.20305}

or a plot of the functon T :

DiscretePlot[ T[n], {n, 100}]

enter image description here

share|improve this answer
