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.

-

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

Questions on Mathematica Stack Exchange are expected to relate to Mathematica within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

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

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


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]


1

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}]


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

-
RSolve[{ t[n + 2] - t[n] - 1/Log[n] == 0, t[0] == 1, t[1] == 1}, t[n], n]


Let's define T :

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


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

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


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}]


-