Average number of comps in successful and unsuccessful search in average binary search tree

Below is the average number of comps of Quicksort  from file 
Average-case_Quicksort_new.pdf

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

Here is its really good approximation experimentally derived with Mathematica

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

where

N[EulerGamma]

0.5772156649015329`

We will use a rougher, but still good (derived experimentally in file Summationa.nb) approximation

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

Since QuickSort is simulated by 
BS-treeSort in that QuickSort builds a 
BS tree T of pivots while sorting and makes 
ipl(T) comparisons of keys, the average number of comparisons done by QuickSort  is the same as the average ipl in an average BS tree. 

So, the average epl in an average BS tree is the above number pus 2n, that is:

2 (n + 1) ((∑_(i=1)^n)(1/i)) - 2 n

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

The average number of comps in a successful search in an average BS tree is
(Subscript[c, n])= (ipl/n)+1 =

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

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

-1.8455686701969345`-(1/(6 (n^3)))+(5/(6 (n^2)))+((2.1544313298030655`)/n)+2 Log[n]+((2 Log[n])/n)

Putting

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

this yields the approximation from the file 
2trees.pdf

1.3862943611198906Log2[n]-1.8455686701969345+(1/n)1.3862943611198906Log2[n]+(2.1544313298030655/n)+(5/(6 (n^2)))-(1/(6 (n^3)))

Here is the graph of the exact value and its approximation

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

Perfect match!

Here is the difference between the two at n=10

Table[(((2 (n + 1) ((∑_(i=1)^n)(1/i)) - 4 n))/n)+1-(1.3862943611198906`Log2[n]-1.8455686701969343`+(1/n)1.3862943611198906`Log2[n]+2.1544313298030655`/n+(5/(6 (n^2)))-(1/(6 (n^3)))),{n,10,10.0004}]

The average number of comps in an unsuccessful search in an average BS tree is
(Subscript[c', n])= (epl/(n+1)) =

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

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

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

((2 n)/(1+n))=((2 n+2-2)/(1+n))=((2 n+2)/(1+n))-(2/(1+n))=((2 (n+1))/(1+n))-(2/(1+n))=2-(2/(1+n))

Together[2-(2/(1+n))]

1.1544313298030657` -(1/(6 (n^2)))+(1/n)-2+(2/(1+n))+2 Log[n]

1.1544313298030657` -2

-0.8455686701969343` -(1/(6 (n^2)))+(1/n)+(2/(1+n))+2 Log[n]

N[2Log[2]]

1.3862943611198906`

This yields the approximation from the file 
2trees.pdf

1.3862943611198906`Log2[n]+-0.8455686701969343`+(1/n)+((2 )/(n+1))-(1/(6 (n^2)))

Here is a graph of the exact value and approximation

Plot[{(1/(n+1))(2 (n + 1) ((∑_(i=1)^n)(1/i)) - 2 n),1.3862943611198906`Log2[n]+-0.8455686701969343`+(1/n)+((2 )/(n+1))-(1/(6 (n^2)))},{n,19980,20000}]

Again, perfect match!

Here is the difference between the two at n=10

Table[(1/(n+1))(2 (n + 1) ((∑_(i=1)^n)(1/i)) - 2 n)-(1.3862943611198906`Log2[n]+-0.8455686701969343`+(1/n)+((2 )/(n+1))-(1/(6 (n^2)))),{n,10,10.0004}]

Here is the difference between (Subscript[c', n]) and (Subscript[c, n])

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

(∑_(i=1)^n)(1/i)

((n(3+n))/(n (1+n)))-((2 (1+n) (∑_(i=1)^n)(1/i))/(n (1+n)))

((n+3)/(n+1))-((2 (∑_(i=1)^n)(1/i))/n)

((n+3)/(n+1))-((2 (Log[n]+0.5772156649015329+(1/(2n))-(1/(12(n^2)))))/n)

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

((n+1)/(n+1))+(2/(n+1))-((2 Log[n])/n)-((1.1544313298030657`)/n)-(1/(n^2))+(1/(6 (n^3)))

1-((2 Log[n])/n)-((1.1544313298030657`)/n)+(2/(n+1))-(1/(n^2))+(1/(6 (n^3)))

or, approximately

1-((2 Log[n])/n)

The red part converges to 0, so the entire expression converges to 1.

Here is a graph of the exact difference between (Subscript[c', n]) and (Subscript[c, n])

DiscretePlot[((n+3)/(n+1))-((2 (∑_(i=1)^n)(1/i))/n),{n,1,100}]

Plot[{((n+3)/(n+1))-((2 (∑_(i=1)^n)(1/i))/n),1},{n,100,1000}]

So, (Subscript[c', n]) ≈ (Subscript[c, n])+1 for large n.

For comparison, here is a graph of both exact and approximate difference

DiscretePlot[{((n+3)/(n+1))-((2 (∑_(i=1)^n)(1/i))/n),1-((2 Log[n])/n)},{n,1,100}]

So, it's pretty good for n≥3.

Here is a graph of the aproximate difference alone

Plot[{1-((2 Log[n])/n)},{n,1,100}]