Analysis of Algorithms : An Active Learning Approach

66 SORTING ALGORITHMS

where, again, C(i) is the number of comparisons done in the first i passes of the

for loop before we stop. So, how many comparisons is this? C(i) is given by

the equation

Substituting this back into the first equation gives the following

BecauseN is a constant relative to i, by using Equations 1.11 and 1.14 we can

get

Again using Equation 1.11 and some basic algebra, we get

Now, we apply Equations 1.15 and 1.16 to get

Ci() j

j=N–1

i

∑ j

j=i

N–1

∑ j

j=1

N–1

∑ j

j=1

i–1

===–∑ the last step by Equation 1.10

Ci() ()N–^1 N

2

----------------------- ()i–^1 i

2

• ----------------- N

(^2) – N–i (^2) +i
2
==-----------------------------------
AN()^1
N– 1
------------- N
(^2) – N–i (^2) +i
2
-----------------------------------
i=1
N–1
= ∑
AN() -------------N^1 – 1 ()N– 1 N
(^2) – N
----------------- 2 -

• i^2 +i
  -------------- 2



i=1

N–1

= * +∑

AN() N

(^2) – N
----------------- 2 -
1
2 ()N– 1
--------------------- –i^2
i=1
N–1
∑ i
i=1
N–1
= + +∑
AN() N
(^2) – N
2
------------------ 2 ---------------------()N^1 – 1 ()N–^1 N()^2 N–^1
6
= + –---------------------------------------------+()----------------------N– 21 N-
AN() N
(^2) – N
----------------- 2 -
N() 2 N– 1

• -------------------------- 12
  N
  = +---- 4

AN()^6 N

(^2) – 6 N– 2 N (^2) ++N 3 N
= ------------------------------------------------------------------ 12 -
AN()^4 N
(^2) – 2 N
12
= ------------------------
AN()≈^13 --N^2 = ON()^2