Quicksort

Author

Eric W. Weisstein
July 1, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/ComputerScience/Quicksort.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Quicksort.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Recurrence

V5

RSolve[{n T[n]==(n+1)T[n-1]+2n-1,T[0]==0},T[n],n]

V7

RSolve[{n T[n]==(n+1)T[n-1]+2n-1,T[0]==0},T[n],n]

FullSimplify[%]

Simplify

FullSimplify[Subtract@@{-3 n+2 (1+n) HarmonicNumber[n],2(n+1)HarmonicNumber[n+1]-3n-2}]

l1=Table[-3 n+2 (1+n) HarmonicNumber[n],{n,0,5}]

a[0]:=0
a[n_]:=a[n]=n+2/n  Total[Table[a[r],{r,0,n-1}]]

a/@Range[0,10]

l2=Table[2(n+1)HarmonicNumber[n+1]-3n-2,{n,0,10}]

Asymptotic

v5

Series[-3 n+2 (1+n) HarmonicNumber[n],{n,∞,1}]

v6

FullSimplify[Normal[Series[-3 n+2 (1+n) HarmonicNumber[n],{n,∞,1}]],n>0]

FullSimplify[Normal[Series[2(n+1)HarmonicNumber[n+1]-3n-2,{n,∞,1}]],n>0]

V7

Series[-3 n+2 (1+n) HarmonicNumber[n],{n,∞,1}]

FullSimplify[Normal[%]]