Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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
4  
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
1  
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 :) –  rm -rf Oct 3 '12 at 16:27
add comment

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.

2 Answers

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

Plots

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

Output

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

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
add comment
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
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.