Solving exactly the recurrence relation for the average-case running time A[n] for QuickSort:

A[n]=n-1+(1/n)(∑_(i=0)^(n-1))(A[i]+A[n-1-i])

A[0]=0

We will find the exact solution

A[n]=2(n+1)(∑_(i=1)^n)(1/i)-4n

and compute its close approximation

A[n]≈1.3862943611198906(n+1)Log2[n]-2.8455686701969345`n+2.1544313298030655`+(5/(6 n))-(1/(6 (n^2)))

the difference between which and the exact A[n] converges to 0 faster than (1/(n^3)).
The part highlighted yellow and its derivation is mandatory for all students; the rest of the aproximation and its derivation is optional - they are shown here for illustration purposes only.

( The textbook approximation was 

A[n] ≈ 1.386n Log2[n]-2.846 n  

- good enough if you don't want to be too accurate, although

A[n] ≈ 1.386(n+1) Log2[n]-2.846 n  +2

is better.)


We have:
 
(∑_(i=0)^(n-1))(A[i]+A[n-1-i]) =

=(∑_(i=0)^(n-1))A[i]+(∑_(i=0)^(n-1))A[n-1-i] =

[putting j = n - 1-i; j ∈ {0,...,n-1}]

=(∑_(i=0)^(n-1))A[i]+(∑_(j=0)^(n-1))A[j]=

=(∑_(i=0)^(n-1))A[i]+(∑_(i=0)^(n-1))A[i]=

=2(∑_(i=0)^(n-1))A[i]

So,

A[n]=n-1+(2/n)(∑_(i=0)^(n-1))A[i]
A[0]=0

Notation change to use Mathematica

(Subscript[A, n])=n-1+(2/n)(∑_(i=0)^(n-1))(Subscript[A, i])

(Subscript[A, n-1])=n-2+(2/(n-1))(∑_(i=0)^(n-2))(Subscript[A, i])

n×(Subscript[A, n]) - (n-1)(Subscript[A, n-1])

Expand[-(-1+n) (-2+n+((2 (∑_(i=0)^(-2+n))(Subscript[A, i]))/(-1+n)))+n (-1+n+((2 (∑_(i=0)^(-1+n))(Subscript[A, i]))/n))]

Factor[-2+2 n+((2 (∑_(i=0)^(-2+n))(Subscript[A, i]))/(-1+n))-((2 n (∑_(i=0)^(-2+n))(Subscript[A, i]))/(-1+n))+2 (∑_(i=0)^(-1+n))(Subscript[A, i])]

2 (-1+n-(∑_(i=0)^(-2+n))(Subscript[A, i])+(∑_(i=0)^(-1+n))(Subscript[A, i]))

2 (-1+n-(∑_(i=0)^(-2+n))(Subscript[A, i])+(∑_(i=0)^(-1+n))(Subscript[A, i])) =2 (-1+n-(∑_(i=0)^(-2+n))(Subscript[A, i])+(∑_(i=0)^(-2+n))(Subscript[A, i])+(∑_(i=-1+n)^(-1+n))(Subscript[A, i]))

2 (-1+n-(∑_(i=0)^(-2+n))(Subscript[A, i])+(∑_(i=0)^(-2+n))(Subscript[A, i])+(∑_(i=-1+n)^(-1+n))(Subscript[A, i]))

2 (-1+n+(Subscript[A, -1+n]))

So,

n×(Subscript[A, n]) - (n-1)(Subscript[A, n-1]) = 2 (-1+n+(Subscript[A, -1+n]))

or

n×(Subscript[A, n])=(n+1)(Subscript[A, n-1]) + 2 (-1+n)

((A[n])/(n+1))== ((A[n-1])/n)+((2(n-1))/(n(n+1))), A[0]==0

Guess: A[n] = 2(n+1)(∑_(i=1)^n)(1/i)-4n

Check:

A[0]=2 1 0-0=0. OK

Let n≥ 2.

((A[n])/(n+1))=2(∑_(i=1)^n)(1/i)-4(n/(n+1))

((A[n-1])/n)=2(∑_(i=1)^(n-1))(1/i)-4((n-1)/n)

((A[n])/(n+1))-((A[n-1])/n)=2(∑_(i=1)^n)(1/i)-2(∑_(i=1)^(n-1))(1/i)-4(n/(n+1))+4((n-1)/n)=(2/n)-4(n/(n+1))+4((n-1)/n)

Factor[(2/n)-4(n/(n+1))+4((n-1)/n)]

So, ((A[n])/(n+1))-((A[n-1])/n)=((2 (-1+n))/(n (1+n)))

or, ((A[n])/(n+1))== ((A[n-1])/n)+((2(n-1))/(n(n+1)))

DONE

Manual check with actual Quicksort: should be 
A[1]=0 
Is 2 2 1-4=0OK

A[2]=1 
Is 2 3 (1+(1/2))-8=9-8=1OK

and 

A[3]=(16/6)=(8/3)
(6 input permutations of 3 elements (1,2,3); 2 of them (2,1,3) and (2,3,1) require 2 comps and the remaining 4 require 3 coms, for a total of 16 comps for 6 input permutations)
Is 2 4 (1+(1/2)+(1/3))-12=8+4+(8/3)-12=(8/3) OK

Manual check: OK

A graph of the exact solution:

Plot[{2(n+1)(∑_(i=1)^n)(1/i)-4n},{n,1,20}]

Let's approximate the exact solution

(∑_(i=1)^n)(1/i)≈Log[n]+EulerGamma+(1/(2n))-(1/(12(n^2)))

2(n+1)(∑_(i=1)^n)(1/i)≈2(n+1)Log[n]+2(n+1)EulerGamma+2(n+1)((1/n)-(1/(12(n^2))))

Factor[2(n+1)((1/(2n))-(1/(12(n^2))))]

Expand[(((1+n) (-1+6 n))/(6 (n^2)))]

1-(1/(6 (n^2)))+(5/(6 n))≈1+(5/(6 n))

So,

2(n+1)(∑_(i=1)^n)(1/i)≈2(n+1)Log[n]+2(n+1)EulerGamma+1+(5/(6 n))

Log2[n]

2Log[n]=2Log[2]Log2[n]

N[2Log[2]]

2Log[n]=1.3862943611198906`Log2[n]

N[EulerGamma]

0.5772156649015329`

N[2EulerGamma]

N[2EulerGamma+1]

2(n+1)(∑_(i=1)^n)(1/i)≈1.3862943611198906(n+1)Log2[n]+1.1544313298030657`n+2.1544313298030655`+(5/(6 n))

Thus

A[n]≈1.3862943611198906(n+1)Log2[n]+1.1544313298030657`n+2.1544313298030655`+(5/(6 n))-4n

N[2EulerGamma-4]

Here is our approximation of A[n]:

A[n]≈1.3862943611198906(n+1)Log2[n]-2.8455686701969345`n+2.1544313298030655`+(5/(6 n))

Plot[{2(n+1)(∑_(i=1)^n)(1/i)-4n,1.3862943611198906(n+1)Log2[n]-2.8455686701969345`n+2.1544313298030655`+(5/(6 n))},{n,1,20}]

Perfect!

Here is a less perfect but still pretty good version:

Plot[{2(n+1)(∑_(i=1)^n)(1/i)-4n,1.3862943611198906(n+1)Log2[n]-2.8455686701969345`n+2.1544313298030655`},{n,1,20}]

Slightly easier to remember approximation:

Plot[{2(n+1)(∑_(i=1)^n)(1/i)-4n,1.386(n+1)Log2[n]-2.85n+2},{n,1,20}]

Here is the textbook approximation:

Plot[{2(n+1)(∑_(i=1)^n)(1/i)-4n,1.386n Log2[n]-2.846n},{n,1,20}]

The class coverage for this file stops here. You don't have to read the rest of this file.

Attempt to soleve with Mathemetica

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

So, the exact solution of the original recurrence relation on the average-case running time of QuickSort is:

A[n]=

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

We will approximate it in more humane terms.

Here is the graph of the exact solution:

Plot[{2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])}, {n,0,10}]

The above shape strongly suggests that it's growth rate is about 

n Log[n].

Here is the plot of both functions:

Plot[Tooltip[{2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n]),n Log[n]}], {n,0,10}]

Indeed, the ratio of the two converges:

Limit[{(2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n]))/(n Log[n])},n-> ∞]

In other words, using Sedgewick's notation ~:

A[n] ~ 2n Log[n]

So,

		A[n] ∈ Θ(n Log2[n])

Now, let's find some other slower growing terms of exact solution A[n].

When we compare the exact solution A[n] to its Θ characterization 2n Log[n], we can notice that the difference between the two approximates a linear function in variable n.

Here is a graph of that difference:

Plot[{(2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n]))-(2n Log[n])},{n,.001,20000}]

In order to find a coefficient of that (approximately) linear function (the slope of the above line), we calculate limit of the mentioned above difference divided by n, that is:

Limit[{(2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])-2n Log[n])/n},n-> ∞]

N[2 (-2+EulerGamma)]

-2.8455686701969345`

N[Log[4]]

1.3862943611198906`

This yields the textbook's approximation:.

2n Log[n]+2 (-2+EulerGamma)n =1.3862943611198906`n Log2[n]-2.8455686701969345`n

But the function

2n Log[n]+2 (-2+EulerGamma)n

does not approximate A[n] well enough when n -> ∞ because the difference between the two diverges to ∞:

Limit[{2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])-2n Log[n]-2 (-2+EulerGamma)n},n-> ∞]

So we need to inject another adjustment to our approximation. We will inject a term of the form constant×Log2[n], because the above mentioned difference is in Θ(Log2[n]), as the following limit proves:

Limit[{(2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])-Log[4]n Log2[n]-2 (-2+EulerGamma)n)/Log[n]},n-> ∞]

{2}

This gives us this improved approximation of A[n]:

2n Log[n]+2 (-2+EulerGamma)n+2Log[n]

or, after grouping the first an the last term,

2(n+1) Log[n]+2 (-2+EulerGamma)n

It yields the approximation 

1.386(n+1) Log2[n]-2.846 n  

mentioned at the begining of this file.

This one is close, but still need another adjustment, constant at this time. We find that constant by letting Mathematica compute the limit of the difference between the exact A[n] and our approximation:

Limit[{2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])-2(n+1) Log[n]-2 (-2+EulerGamma)n},n-> ∞]

= 1+2EulerGamma

N[1+2EulerGamma]

So, the function

Log[4](n+1) Log2[n]+2 (-2+EulerGamma)n+(1+2EulerGamma)=
=1.3862943611198906`(n+1)Log2[n]-2.8455686701969345`n+2.1544313298030655`
asympthotically approaches A[n] as n -> ∞. In particular, the difference between the two converges to 0, as the following limit shows:

Limit[{2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])-(2n Log[n]+2 (-2+EulerGamma)n+2Log[n]+(1+2EulerGamma))},n-> ∞]

Here is a graph of the difference between the exact A[n] and our approximation:

Plot[{2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])-(2n Log[n]+2 (-2+EulerGamma)n+2Log[n]+(1+2EulerGamma))},{n,2,2000000}]

So, it is close, indeed.

Here is our approximation, again, in even more humane terms:

1.3862943611198906`(n+1)Log2[n]-2.8455686701969345`n+2.1544313298030655`

Here is a series of plots of the exact solution (blue line) plotted against out approximation (purple line) and textbook's approximation (olive line):

Plot[Tooltip[{2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n]),1.3862943611198906`(n+1)Log2[n]-2.8455686701969345`n+2.1544313298030655`,1.386n Log2[n]-2.846 n}], {n,0,5}]

Plot[Tooltip[{2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n]),1.3862943611198906`(n+1)Log2[n]-2.8455686701969345`n+2.1544313298030655`,1.386n Log2[n]-2.846 n}], {n,5,10}]

Plot[Tooltip[{2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n]),1.3862943611198906`(n+1)Log2[n]-2.8455686701969345`n+2.1544313298030655`,1.386n Log2[n]-2.846 n}], {n,10000,10001}]

The rest of this file is optional - recommended for the brightest and most diligent students.

Below is another approximation that does not use Euler's gamma but uses harmonic number, instead:

Simplify[(Log[4]n Log2[n]+2 (-2+EulerGamma)n+Log[4]Log2[n]+(1+2EulerGamma))]

Simplify[(2Log[2]n Log2[n]+2 (-2+EulerGamma)n+2Log[2]Log2[n]+(1+2EulerGamma))]

2(n+1)(Log[n]+EulerGamma)-4n+1 ≈
2(n+1)((∑_(i=1)^n)(1/i))-4n

The two coincide for integer arguments, as the graph below shows.

Plot[{2(n+1)((∑_(i=1)^n)(1/i))-4n,2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])},{n,1,20}]

Plot[{2(n+1)((∑_(i=1)^n)(1/i))-4n,2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])},{n,21,40}]

Plot[{2(n+1)((∑_(i=1)^n)(1/i))-4n,2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])},{n,41,60}]

Plot[{2(n+1)((∑_(i=1)^n)(1/i))-4n,2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n]),2(n+1)(Log[n]+EulerGamma)-4n+1 },{n,1,10}]

Using

2Log[n] = 2Log[2]Log2[n]

N[2Log[2]]

we obtain:



A[n] ≈ 

1.3862943611198906`(n+1)Log2[n]-2.8455686701969345` n+2.1544313298030655`

Plot[{2(n+1)((∑_(i=1)^n)(1/i))-4n,1.3862943611198906`(n+1)Log2[n]-2.8455686701969345` n+2.1544313298030655`,2(n+1)(Log[n]+EulerGamma)-4n+1 },{n,1,10}]

The above approximation was used as a reference in the demo program that counted number of comparisons done by QuickSort that I run for you in class.

Obviously, the approximation we computed (with a help from Mathematica) is Θ(n Log2[n]), because the limit of the ratio of the approximation to n Log2[n] is greater than 0 and less than ∞:

Limit[{(1.3862943611198906`(n+1)Log2[n]-2.8455686701969345` n+2.1544313298030655`)/(n Log2[n])},n-> ∞]

Now, we will find an approximation of A[n] that converges to A[n] when n -> ∞ faster than (1/n) converges to 0 when n -> ∞.

Limit[{n(2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])-(Log[4]n Log2[n]+2 (-2+EulerGamma)n+Log[4]Log2[n]+(1+((EulerGamma Log[16])/(Log[4])))))},n-> ∞]

Limit[{n(2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])-(Log[4]n Log2[n]+2 (-2+EulerGamma)n+Log[4]Log2[n]+(1+((EulerGamma Log[16])/(Log[4])))+(5/(6n))))},n-> ∞]

Limit[{n(2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])-(2Log[2]n Log2[n]+2 (-2+EulerGamma)n+2Log[2]Log2[n]+(1+2EulerGamma)+(5/(6n))))},n-> ∞]

N[2Log[2]n Log2[n]+2 (-2+EulerGamma)n+2Log[2]Log2[n]+(1+2EulerGamma)+(5/(6n))]

N[2Log[2] Log2[n](n+1)+2 (-2+EulerGamma)n+(1+2EulerGamma)+(5/(6n))]

N[5/6]

So,

A[n] ≈ 

1.3862943611198906`(n+1)Log2[n]-2.8455686701969345` n+2.1544313298030655`+ (1/n)0.8333333333333334`

Plot[(2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])-(Log[4]n Log2[n]+2 (-2+EulerGamma)n+Log[4]Log2[n]+(1+((EulerGamma Log[16])/(Log[4])))+(5/(6n)))),{n,2,20000}]

Here is comparision with exact solution that uses harmonic number:

DiscretePlot[(2(n+1)((∑_(i=1)^n)(1/i))-4n-(Log[4]n Log2[n]+2 (-2+EulerGamma)n+Log[4]Log2[n]+(1+((EulerGamma Log[16])/(Log[4])))+(5/(6n)))),{n,2,2000}]

Here is another approximation:

Limit[{(n^32)(((∑_(i=1)^n)(1/i))- (Log[n]+EulerGamma+(1/(2n))-(1/(12(n^2)))+(1/(120(n^4)))-(1/(252(n^6)))+(1/(240(n^8)))-(1/(132(n^10)))+(691/(32760(n^12)))-(1/(12(n^14)))+(3617/(8160(n^16)))-(43867/(14364(n^18)))+(174611/(6600(n^20)))-(77683/(276(n^22)))+(236364091/(65520(n^24)))-(657931/(12(n^26)))+(3392780147/(3480(n^28)))-(1723168255201/(85932(n^30)))+(7709321041217/(16320(n^32)))))},n-> ∞]

Plot[{2(n+1)(Log[n]+EulerGamma+(1/(2n))-(1/(12(n^2)))+(1/(120(n^4)))-(1/(252(n^6)))+(1/(240(n^8)))-(1/(132(n^10)))+(691/(32760(n^12)))-(1/(12(n^14)))+(3617/(8160(n^16)))-(43867/(14364(n^18)))+(174611/(6600(n^20)))-(77683/(276(n^22)))+(236364091/(65520(n^24)))-(657931/(12(n^26)))+(3392780147/(3480(n^28)))-(1723168255201/(85932(n^30)))+(7709321041217/(16320(n^32))))-4n,1.386n Log2[n]-2.846 n,2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])},{n,2,5}]

Limit[{(n^33)(2(n+1)(Log[n]+EulerGamma+(1/(2n))-(1/(12(n^2)))+(1/(120(n^4)))-(1/(252(n^6)))+(1/(240(n^8)))-(1/(132(n^10)))+(691/(32760(n^12)))-(1/(12(n^14)))+(3617/(8160(n^16)))-(43867/(14364(n^18)))+(174611/(6600(n^20)))-(77683/(276(n^22)))+(236364091/(65520(n^24)))-(657931/(12(n^26)))+(3392780147/(3480(n^28)))-(1723168255201/(85932(n^30)))+(7709321041217/(16320(n^32))))-4n-2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n]))},n-> ∞]

So, here is a really close approximation with the error converging to 0 faster than (1/(n^31)):

A[n] ≈2(n+1)(Log[n]+EulerGamma+(1/(2n))-(1/(12(n^2)))+(1/(120(n^4)))-(1/(252(n^6)))+(1/(240(n^8)))-(1/(132(n^10)))+(691/(32760(n^12)))-(1/(12(n^14)))+(3617/(8160(n^16)))-(43867/(14364(n^18)))+(174611/(6600(n^20)))-(77683/(276(n^22)))+(236364091/(65520(n^24)))-(657931/(12(n^26)))+(3392780147/(3480(n^28)))-(1723168255201/(85932(n^30)))+(7709321041217/(16320(n^32))))-4n

Expand[2(n+1)(Log[n]+EulerGamma+(1/(2n))-(1/(12(n^2))))-4n]

N[1+2 EulerGamma-(1/(6 (n^2)))+(5/(6 n))-4n+2 EulerGamma n+2 Log[n]+2 n Log[n]]

2.1544313298030655` -((0.16666666666666666`)/(n^2))+((0.8333333333333334`)/n)-2.8455686701969345` n+2(n+1)n Log[n]

1.3862943611198906`(n+1)Log2[n]

2.` (1+n) Log[n]

A[n] ≈ 

1.3862943611198906`(n+1)Log2[n]-2.8455686701969345` n+2.1544313298030655`+ (1/n)0.8333333333333334`-((0.16666666666666666`)/(n^2))

Plot[Tooltip[{2.1544313298030655` -((0.16666666666666666`)/(n^2))+((0.8333333333333334`)/n)-2.8455686701969345` n+2.` Log[n]+2.` n Log[n], 1.386n Log2[n]-2.846 n,2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])}],{n,1,4}]

Plot[Tooltip[{2.1544313298030655` -((0.16666666666666666`)/(n^2))+((0.8333333333333334`)/n)-2.8455686701969345` n+2.` Log[n]+2.` n Log[n], 1.386n Log2[n]-2.846 n,2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])}],{n,1,20}]

Plot[Tooltip[{2.1544313298030655` -((0.16666666666666666`)/(n^2))+((0.8333333333333334`)/n)-2.8455686701969345` n+2.` Log[n]+2.` n Log[n], 1.386n Log2[n]-2.846 n,2 (EulerGamma-2 n+EulerGamma n+PolyGamma[0,1+n]+n PolyGamma[0,1+n])}],{n,3000,3001}]