3
$\begingroup$

In the book An Introduction to the Analysis of Algorithms there is a recurrence relation for the number of compares used in Quicksort algorithm: $$ C_N=N+1+\sum_{0≤k≤N-1}\frac{1}{N}(C_k+C_{N−k−1}) $$ (See http://aofa.cs.princeton.edu/10analysis/ for details)

This recurrence relation is already solved in the book: $$ C_N = 2(N+1)H_N - 2N,$$ where $ H_N $ are harmonic numbers.

Now I'm trying to solve it using Mathematica:

RSolve[{c[n] == n + 1 + 1/n*Sum[c[k] + c[n - k - 1], {k, 0, n - 1}], 
        c[0] == 0}, c[n], n]

Unfortunately, I can't get a result: RSolve just pretty prints input and doesn't solve anything.

Is there any way to solve such recurrences using Mathematica? Are there any other CASes which able to solve it?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

You can define c[n] with

c[n_] := c[n] = n + 1 + 1/n*Sum[c[k] + c[n - k - 1], {k, 0, n - 1}]
c[0] = 0;

and then use FindSequenceFunction to find the desired solution:

FindSequenceFunction[Table[c[n], {n, 1, 10}], n]

2 (1 + n) (-1 + EulerGamma + PolyGamma[0, 2 + n])

FullSimplify@%

2 (1 + n) (-1 + HarmonicNumber[1 + n])

%% == 2 (n + 1) HarmonicNumber[n] - 2 n // FullSimplify

True
Improve this answer
$\endgroup$
3
  • $\begingroup$ Dear Karsten, small question: what if instead of the condition c[0]=0 we had one of the kind c[n<2]=0, how do we express this in mathematica when defining and solving recurrence relations as you have exactly done in the above. Thanks in advance for any hints. $\endgroup$
    – user21766
    Commented Jul 14, 2017 at 13:33
  • $\begingroup$ @user929304 You can use a PatternTest, a Condition, or Piecewise. $\endgroup$
    – Karsten7
    Commented Jul 14, 2017 at 20:10
  • $\begingroup$ In my answer I could have used, e. g., c[n_?(# <= 0 &)] = 0;, c[n_ /; n <= 0] = 0;, or c[n_] /; n <= 0 := c[n] = 0; instead of c[0] = 0; or just c[n_] := c[n] = \[Piecewise] { {0, n <= 0}, {n + 1 + 1/n*Sum[c[k] + c[n - k - 1], {k, 0, n - 1}], n > 0} } for both cases. $\endgroup$
    – Karsten7
    Commented Jul 14, 2017 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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