arXiv:1611.04784v1 [] 15 Nov 2016

Rate of Convergence of Major Cost
Incurred in the In-Situ Permutation Algorithm
Sumit Kumar Jha
Abstract. The in-situ permutation algorithm due to MacLeod replaces (x1 , · · · , xn ) by
(xp(1) , · · · , xp(n) ) where π = (p(1), · · · , p(n)) is a permutation of {1, 2, · · · , n} using at most
O(1) space. Kirshenhofer, Prodinger and Tichy have shown that the major cost incurred in the
algorithm satisfies a recurrence similar to sequence of the number of key comparisons needed
by the Quicksort algorithm to sort an array of n randomly permuted items. Further, Hwang
has proved that the normalized cost converges in distribution. Here, following Neininger and
Rüschendorf, we prove the that rate of convergence to be of the order Θ(ln(n)/n) in the Zolotarev
metric.

1. Introduction
The in-situ permutation algorithm developed by MacLeod [4] replaces (x1 , · · · , xn ) by
(xp(1) , · · · , xp(n) ) where π = (p(1), · · · , p(n)) is a permutation of {1, 2, · · · , n} using at most O(1)
space. Kirshenhofer, Prodinger and Tichy [2] have shown that assuming the input comes from a
sequence of independently and identically distributed random variables with a common continuous
distribution, the major cost measures, say Xn , incurred in the algorithm, can be described by
X0 = 0, and for n ≥ 1,
d

∗
Xn = XIn + Xn−1−I
+ In ,
n

(1.1)

d

where (Xn ), (Xn∗ ), (In ) are independent, Xn = Xn∗ , and In is uniformly distributed over {0, 1, · · · , n−
d
1}. Here the symbol = denotes equivalence in distribution.
The mean and variance of Xn were calculated by Knuth [3] which satisfy
E(Xn ) = n ln n + (γ − 2)n + O(ln n), Var(Xn ) = σ 2 n2 − n ln(n) + O(n)
p
where γ denotes Euler’s constant and σ := 2 − π 2 /6 > 0.
Further, Hwang [1] showed using Rösler’s contraction method that
Yn :=

Xn − E(Xn ) d
−
→Y
n

d

where −
→ denotes convergence in distribution. Here Y satisfies
d

Y = U Y + (1 − U )Y ∗ + C(U )

(1.2)
d

where Y = Y ∗ , U is the uniform random variable over the unit interval, Y, Y ∗ , and U are independent, and C(u) := (1 − u) ln(1 − u) + u ln(u) + u.
We wish to estimate the rate of convergence Yn → Y following Neininger and Rüschendorf
[5]. The basic distance considered in [5] is the Zolotarev metric ζ3 which given distributions
L(V ), L(W ) is defined by
ζ3 (L(V ), L(W )) := sup |Ef (V ) − Ef (W )|,
f ∈F3
1

2

SUMIT KUMAR JHA

where F3 := {f ∈ C2 (R, R) : |f 00 (x) − f 00 (y)| ≤ |x − y|} is the space of all twice differentiable
functions with second derivative being Lipschitz continuous with Lipschitz constant 1. Hereon we
use the notation ζ3 (V, W ) := ζ3 (L(V ), L(W )). It is known that convergence in ζ3 implies weak
convergence and that ζ3 (V, W ) < ∞ if EV = EW , EV 2 = EW 2 , and ||V ||3 , ||W ||3 < ∞. The
metric ζ3 is ideal of order 3, that is, we have for T independent of (V, W ) and c 6= 0
ζ3 (V + T, W + T ) ≤ ζ3 (V, W ),

ζ3 (cV, cW ) = |c|3 ζ3 (V, W ).

We wish to obtain following
Theorem 1.1. The major cost (Xn ) incurred in the in-situ permutation algorithm satisfying
recurrence (1.1) satisfies
!


log(n)
Xn − E(Xn )
p
,X = Θ
, (n → ∞)
ζ3
n
Var(Xn )
where X := Y /σ is a scaled version of the limiting distribution in (1.2).
We modify the proof in [5] suited for the above case in the next section.
Notation: Subsequently, we use that Var(Y ) = σ, ||Y ||3 < ∞ where ||Y ||p := (E|Y |p )1/p ,
1 ≤ p < ∞ denotes the Lp -norm.
2. The Proof
We start with the following lemma from [5].
Lemma 2.1. Let V, W have identical first and second moment with ||V ||3 , ||W ||3 < ∞, then
1
1
(2.1)
|EV 3 − EW 3 | ≤ ζ3 (V, W ) ≤ (||V ||23 + ||V ||3 ||W ||3 + ||W ||23 )l3 (V, W )
6
6
where
(2.2)

d

d

lp (L(V ), L(W )) := lp (V, W ) := inf{||V − W ||p : V = V, W = W },

p ≥ 1.

Proof of Theorem 1.1. The constants σ(n) ≥ 0 are defined by
 
1
ln(n)
2
2
+O
.
(2.3)
σ (n) := Var(Yn ) = σ −
n
n
Lower Bound: Establishing the lower bounds only requires information of moments of (Xn ).
Using the bound in lemma 2.1, we have
!

3
 3
Xn − E(Xn )
1
Yn
Y
p
ζ3
,X ≥
E
−E
6
σ(n)
σ
Var(Xn )
Observe that the third moment of Yn is
 
1
1
1
3
3
EYn = 3 E(Xn − E(Xn )) = 3 κ3 (Xn ) = M3 + O
n
n
n
with M3 = E(Y 3 ) > 0 where we use the expansion of third cumulant κ3 (Xn ) of Xn which can
be explicitly computed using generating functions for factorial moments with aid of Maple in [2].
The equation (2.3) gives us
 
1
1
1
3 ln(n)
=
+
+
O
,
σ 3 (n)
σ3
2σ 5 n
n
and thus

3
 3
 
1
Yn
Y
M3 ln(n)
1
E
−E
=
+
O
6
σ(n)
σ
4σ 5 n
n
which proves the claimed lower bound in the theorem.
Upper Bound: The variates Yn would satisfy the recurrence:
n − 1 − In 0
d In
(2.4)
Yn =
YIn +
Yn−1−In + Cn (In ), n ≥ 1,
n
n

RATE OF CONVERGENCE OF MAJOR COST

3

d

where (Yn ), (Yn0 ), In are independent, Yk = Yk0 for all k ≥ 0 and Cn (k) := n1 (µ(k) + µ(n − 1 − k) −
µ(n) + k), with µ(n) := E(Xn ), n ≥ 0. The rest of the proof follows identically as in the upper
bound proof in [5].

References
1. Hsien-Kuei Hwang and Ralph Neininger, Phase change of limit laws in the quicksort recurrence under varying
toll functions, SIAM Journal on Computing 31 (2002), no. 6, 1687–1722.
2. P. Kirschenhofer, H. Prodinger, and R.F. Tichy, A contribution to the analysis of in situ permutation, Glasnik
Mathematicki 22(42) (1987), 269–278.
3. D.E. Knuth, Mathematical analysis of algorithms, Information Processing 71 (1972), 19–22.
4. Iain D. G. Macleod, An algorithm for in-situ permutation., Australian Computer Journal 2 (1970), no. 1, 16–19.
5. Ralph Neininger and Ludger Rüschendorf, Rates of convergence for quicksort, Journal of Algorithms 44 (2002),
no. 1, 52–62.
Center for Security, Theory, and Algorithmic Research, International Institute of Information
Technology, Hyderabad, India
E-mail address: kumarjha.sumit@research.iiit.ac.in

