Graph of numbers of comps of sorting programs and the information-theoretic lower bound

1. Worst case

Lower bound:  ⌈lg n!⌉

DiscretePlot[Tooltip[{⌈Log2[n!]⌉,n⌈Log2[n]⌉-(2^(⌈Log2[n]⌉))+1,(∑_(k=1)^n)⌈Log2[(3/4)k]⌉}],{n,1,23}]

DiscretePlot[Tooltip[{⌈Log2[n!]⌉,n⌈Log2[n]⌉-(2^(⌈Log2[n]⌉))+1,(∑_(k=1)^n)⌈Log2[(3/4)k]⌉}],{n,23,47}]

DiscretePlot[Tooltip[{⌈Log2[n!]⌉,(∑_(k=1)^n)⌈Log2[(3/4)k]⌉}],{n,1,24}]

DiscretePlot[Tooltip[{⌈Log2[n!]⌉,(∑_(k=1)^n)⌈Log2[(3/4)k]⌉}],{n,24,47}]

DiscretePlot[Tooltip[{⌈Log2[n!]⌉,n⌈Log2[n]⌉-(2^(⌈Log2[n]⌉))+1,(∑_(k=1)^n)⌈Log2[(3/4)k]⌉}],{n,1,50}]

Plot[Tooltip[{⌈Log2[n!]⌉,n⌈Log2[n]⌉-(2^(⌈Log2[n]⌉))+1,(∑_(k=1)^n)⌈Log2[(3/4)k]⌉}],{n,1000,1200},PlotPoints-> 2000]

Recall the approximate value of the lower bound on the worst-case:

⌈(n+(1/2)) Log2[n]-1.44 n+1.33⌉

2. Average case

Lower bound: lg n! + ϵ(n!)

DiscretePlot[Tooltip[{Log2[n!]+ϵ[n!],⌈Log2[n!]⌉}],{n,1,10},PlotTheme->"Classic"]

where

β[x_]:=1+x-(2^x)

θ[x_]:=⌈x⌉-x

ϵ[x_]:=β[θ[Log2[x]]]

DiscretePlot[Tooltip[{Log2[n!]+ϵ[n!],⌈Log2[n!]⌉}],{n,10,20},PlotTheme->"Classic"]

DiscretePlot[Tooltip[{Log2[n!]+ϵ[n!],⌈Log2[n!]⌉}],{n,100,110},PlotTheme->"Classic"]

Recall approximate value of the lower bound on the average:

(n+(1/2)) Log2[n]-1.44 n+1.33+ϵ[n!]≈

(the following is an underestimate)

≈(n+(1/2)) Log2[n]-1.44 n+1.33