The simple problems of comparing fractions (Gosper's algorithms for continued fractions from the Hacker's Memorandum) and of deciding the orientation of triangles in computational geometry lead to a complexity analysis with an incursion into a surprising variety of domains: dynamical systems (symbolic dynamics), number theory (continued fractions), special functions (multiple zeta values), functional analysis (transfer operators), numerical analysis (series acceleration), and complex analysis (Riemann hypothesis). These domains all eventually contribute to a detailed characterization of the complexity of comparison and sorting algorithms, either on average or in probability. (Joint work with Brigitte Vallée.)

^{(l)}=1+ 

+ 



and 

^{(l)}= 



(  f=  (  1+(5)^{1/2}  )  /2  )  . 
z 

(s,t)= 



and  z 

(s,t)= 



, 

^{(2)} = 

+ 

z 

(2,2) =17 

(  24Li_{4}  (  1/2  )  p^{2}(ln2)^{2}+21z(3)ln 2+(ln 2)^{4}  )  =1.35113157... 

(n)=n 

(1)^{l1} 


^{(l+1)}=K_{0}nln n+K_{1} n +Q(ln n)+O(1), 
K_{0}= 

and K_{1}=18 

+9 

72 

 

. 
http://algo.inria.fr/flajolet
and http://www.info.unicaen.fr/~brigitte
.
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
.http://www.mathsoft.com/asolve/constant/constant.html
.This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.