COMBINING SEVERAL ALGORITHMS INTO A SUPERIOR ONE
OPTIMAL SYNTHESIS OF MULTIPLE ALGORITHMS 
KERRY M. SOILEAU 
ksoileau@yahoo.com
JULY 27, 2004 
ABSTRACT 
In this paper we give a definition of “algorithm,” “finite algorithm,” “equivalent algorithms,” and what it means for a 
single algorithm to dominate a set of algorithms. We define a derived algorithm which may have a smaller mean 
execution time than any of its component algorithms. We give an explicit expression for the mean execution time 
(when it exists) of the derived algorithm. We give several illustrative examples of derived algorithms with two 
component algorithms. We include mean execution time solutions for two-algorithm processors whose joint density of 
execution times are of several general forms. For the case in which the joint density for a two-algorithm processor is a 
step function, we give a maximum-likelihood estimation scheme with which to analyze empirical processing time data. 
mailto:ksoileau@yahoo.com
1 INTRODUCTION 
It can categorically be said that no algorithm is unique. By this we mean that for a given 
task, invariably more than one algorithm exists which will accomplish that task. One 
strategy is to select one algorithm deemed generally superior to the rest, and to use that 
algorithm exclusively. This paper examines an alternative strategy. We ask, given two or 
more equivalent algorithms, is it ever possible to create a new derived algorithm whose 
mean execution time is less than that of all of the original algorithms? If so, how can such 
an algorithm be derived? 
First we define clearly what we mean by the term “algorithm:”  
Algorithm: An algorithm α  is a pair ( ),α αρ π , where :αρ Ω→Γ  is a Turing-
computable mapping of a countable set Ω  (tasks) into a countable set Γ  (outputs), and 
:απ Ω→  is a mapping of  into the positive real numbers. The function Ω αρ  specifies 
the algorithm’s output ( )αρ ω  when presented with the task ω∈Ω . The function απ  
specifies the execution time ( )απ ω  required to compute the output ( )αρ ω . Note that 
under this definition, given a task ω∈Ω , an algorithm will always produce a definite 
output, namely ( )αρ ω , and will always produce this output after a definite amount of 
time has passed, namely ( )απ ω . We do not address procedures which are 
nondeterministic or whose execution time is unpredictable. 
Definition: We say that an algorithm ( ),α αα ρ π=  is finite if and only if  
for every 
( )0 απ ω< < ∞
ω∈Ω . Note that “ ( ),α αα ρ π=  is finite” does not imply “ απ  is bounded.” For 
example, Quicksort and Bubblesort are finite. 
Definition: We say that two algorithms ( ),α αα ρ π=  and ( ),β ββ ρ π=  are equivalent if 
and only if Dom Dom α βρ ρ=  and ( ) ( )α βρ ω ρ ω=  for every ω∈Ω . Notice that 
equivalent algorithms may require different times to process a given task. For example, 
Quicksort and Bubblesort are equivalent. 
Definition: Let { }1 2, , , Nα α α  be a set of equivalent algorithms. We say that nα  
dominates { }1 2, , , Nα α α  if and only if for every ω∈Ω , ( ) (n iα α )π ω π ω≤  for every 
{ }1,2, ,i N∈ . 
Now suppose we are given a set of finite equivalent algorithms { }1 2, , , Nα α α  such that 
no nα  dominates { }1 2, , , Nα α α . Suppose further that there exists a probability space 
 over  such that ( ), , PΩ ℑ Ω
, , ,
Nα α α
π π π  are random variables. Let 
 be the joint density of the random variables 
, , , :
α α απ π π
, , ,
Nα α α
π π π . 
Definition of Derived Algorithm: From a set of finite equivalent algorithms 
{ }1 2, , , Nα α α , and a given point ( ) [ )
1 2 1, , , 0,
Nτ τ τ
− ∈ ∞ , the function 
 is defined as follows. For each 
, we define the random variable 
1 2 11 2 1
| | | :
NN Nτ τ τ
α α α α
⎡ Ω→ Γ⎣ ⎤⎦
( ) [ ) 11 2 1, , , 0,
Nτ τ τ
− ∈ ∞
, , , 1 2 1, , , :
NT α α απ π π τ τ τ − Ω→  
as follows: 
( )( )
, , , 1 2 1
1 2 2 3
1 2 2 2
1 2 1 1
, , ,
α α απ π π
τ τ τ ω
π ω ω
τ π ω ω
τ τ π ω ω
τ τ τ π ω ω
τ τ τ π ω ω
⎪ + + ∈⎪
⎪ + + + + ∈
⎪ + + + + ∈⎩
     (1) 
1 2 1
1 2 1
| | |
τ τ τ
ρ ω ω
ρ ω ω
ρ ω ω
α α α α ω
ρ ω ω
ρ ω ω
⎪ ∈⎪⎡ ⎤ = ⎨⎣ ⎦
   (2) 
where ( ) ( ) ( ){ }
1 21 2
; , , ,
S α α αω τ π ω τ π ω τ π ω= ∈Ω < < <  for 1 1n N≤ ≤ − . Each  
is the event consisting of the points 
ω∈Ω  on which none of the algorithms 1 2, , , nα α α  
completes processing within each algorithm’s permitted run time limit. The derived 
algorithm is then defined to be the pair 
.  ( )( )1 2 1 1 21 2 1 , , , 1 2 1| | | , , , ,N NN N NT α α ατ τ τ π π πα α α α τ τ τ−− −⎡ ⎤⎣ ⎦
( )( )
, , , 1 2 1, , ,
NT α α απ π π τ τ τ ω−  represents the time taken for the derived algorithm to 
execute when presented with the task ω , and 
1 2 11 2 1
| | |
NNτ τ τ N
α α α α
⎡ ⎤⎣ ⎦  represents the 
derived algorithm’s output when presented with the task ω .  
We may envision an implementation of this algorithm as follows. When presented with a 
task ω∈Ω , a timer is started, and 1α  is applied. If 1α  has not completed by time 1τ , 1α  
is abandoned and 2α  is applied. If 2α  has not completed by time 1 2τ τ+ , 2α  is 
abandoned and 3α  is applied, and so on. If 1Nα −  has not completed by time 
1 2 1Nτ τ τ −+ + + 1N, α −  is abandoned and Nα  is applied and (unlike the other algorithms) 
is allowed to run without time limit. ( )
ρ ω  is returned as output , where iα  is the 
algorithm which completed execution on the task ω∈Ω . 
The expected value (if it exists) of the random variable ( )
, , , 1 2 1, , ,
NT α α απ π π τ τ τ −  is 
given by the following  
Theorem 1: 
( ) ( ) ( )
( ) ( ) ( ) ( )
, , , 1 2 1 1 1
1 1 1
, , ,
n n n n N N
ET E S P S
E S S P S S E S P S
α α απ π π α
τ τ τ π
− − −
= Ω Ω
∼ ∼ 1−
Proof: Recall that 
( )( )
, , , 1 2 1
1 2 2 3
1 2 2 2
1 2 1 1
, , ,
α α απ π π
τ τ τ ω
π ω ω
τ π ω ω
τ τ π ω ω
τ τ τ π ω ω
τ τ τ π ω ω
⎪ + + ∈⎪
⎪ + + + + ∈
⎪ + + + + ∈⎩
It follows immediately that 
( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
, , , 1 2 1
1 1 2 1 2
1 2 2 3 2 3
1 2 2 2 1 2 1
1 2 1 1 1
, , ,
N N N N
N N N
E S P S
E S S P S S
E S S P S S
E S S P
E S P S
α α απ π π
τ τ τ
τ τ π
τ τ τ π
τ τ τ π
− − − −
− − −
= Ω Ω
+ + +
+ + + + +
+ + + + +
∼ NS S −∼
    (4) 
This may be written as  
 ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( ) ( ) ( )
, , , 1 2 1 1 1 1 1 2
1 2 1 2 1 2 2 3
2 3 2 3
1 2 2 2 1
2 1 2 1
1 2 1 1 1 1
, , ,
N N N
N N N N
N N N N
ET E S P S P S S
E S S P S S P S S
E S S P S S
P S S
E S S P S S
P S E S P S
α α απ π π α
τ τ τ π τ
π τ τ
τ τ τ
τ τ τ π
− − −
− − − −
− − − −
= Ω Ω +
+ + +
+ + + + +
+ + + + +
∼ ∼ ∼
∼ ∼ ∼
∼ ∼   
Telescoping sums yield
 ( ) ( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( ) ( ) ( )( )
( ) ( ) ( )( ) ( )( )
, , , 1 2 1 1 1
1 2 1 2
2 3 2 3
2 1 2 1
1 1 2 2 3 2 1 1
2 2 3 2 1 1 1 1
, , ,
N N N N
N N N
N N N N N
ET E S P S
E S S P S S
E S S P S S
E S S P S S
E S P S
P S S P S S P S S P S
P S S P S S P S P S
α α απ π π α
τ τ τ π
− − − −
− − −
− − − − −
= Ω Ω
+ + + + +
+ + + + + +
∼ ∼ ∼
Next,
( ) ( ) ( )
( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( )
, , , 1 2 1 1 1
1 2 1 2
2 3 2 3 2 1 2 1
1 1 1 1 2 2 1 1
, , ,
N N N N
N N N N
ET E S P S
E S S P S S
E S S P S S E S S P S S
E S P S P S P S P S
α α απ π π α
τ τ τ π
π τ τ τ
− − −
− − − −
= Ω Ω
+ + +
+ + + + +
∼ ∼ ∼ ∼ −
whence 
( ) ( ) ( )
( ) ( ) ( ) ( ) (
, , , 1 2 1 1 1
1 1 1 1
, , ,
n n n n N N n
ET E S P S
)nE S S P S S E S P S P S
α α απ π π α
τ τ τ π
− − − −
= Ω Ω
+ +∑ ∑
∼ ∼ τ+
as desired.
2 CASE  (TWO ALGORITHMS) 2N =
In this case 
( )( )
( ) ( )
( ) ( )
π ω π ω
τ π ω τ π ω
+ <⎪⎩       
( ) ( ) ( ) ( ) ( ) ( )
1 21 2
, 1 1 1 1 1 1 1ET E S P S E S P S P Sα απ π α ατ π π τ= Ω Ω + +∼ ∼
 and 
( ){ }
;S αω τ π ω= ∈Ω < ,        (11) 
( ) ( ) ( ) ( )( ) ( )1 1 1 2 1 11 2, 1 1 1 1 1 1ET E P E Pα απ π α α α α α ατ π π τ π τ π τ π τ τ π= ≤ ≤ + < + <  (12) 
2.1 ( )
, 1ET α απ π τ  WHEN JOINT DENSITY IS ( )1 2, ,f x yα απ π  
In this case, 
( ) ( ) ( ) ( )
1 2 1 2 1 2
, 1 , 1 ,
0 0 0
,ET xf x y dydx y f x y dydx
α α α α α α
π π π π π π
∞ ∞ ∞
= + +∫ ∫ ∫ ∫ ,    (13) 
2.11 EXAMPLE 
Suppose the joint density of completion times for the two algorithms is given by 
( ) ( )(
, , 12 exp )f x y xy x yα απ π = − +        (14) 
Figure 1. 
,f α απ π  
Then 
( ) ( )( )( ) ( ) ( )
4 2 3 23 3
, 1 1 1 1 1 1 12 8erf 1 expET α απ π τ π τ τ τ τ τ τ= − + + + − + π   (15) 
Figure 2. 
,ET α απ π  
2.12 EXAMPLE 
Suppose the joint density of completion times for the two algorithms is given by 
( ) ( )
, , 48 exp 4 3f x y xy x yα απ π = − −
       
Figure 3. 
,f α απ π  
Then 
( ) ( ) ( )
, 1 1 14 6erf 2 3 exp 4ET α απ π τ π τ π τ= + −      (17) 
Figure 4. 
,ET α απ π  
2.13 EXAMPLE 
Suppose the joint density of completion times for the two algorithms is given by 
( ) ( )( )
( ) ( )( )1 2
, 2 2
exp 1 7
, .022179119694367830844
exp 7 1
f x y xy
α απ π
⎛ ⎞− − − −
⎜ ⎟= ⎜ ⎟
+ − − − −⎜ ⎟
   (18) 
Figure 5. 
,f α απ π  
Figure 6. 
,ET α απ π  
The minimum occurs at 1 2.492τ . Note that if 1 2.492τ , then ( )
, 1 2.854ET α απ π τ , 
while 
4.260E απ  and 2 4.260E απ . In this case the derived algorithm has better mean 
execution time than either of the original algorithms. Its mean execution time is 
approximately 33% less than that of either of the original algorithms. 
Notation: In the following, wherever 1 2, , , MB B B  is found in a context requiring a 
Boolean expression, it means the conjunction 1 2 MB B B∧ ∧ ∧  of the Boolean 
expressions 1 2, , , MB B B .
Notation: In the following, if B  is a Boolean expression, then ( ) .  
1  is tru
0  is fals
In particular we define ( )
a x b a x x b
≤ < ≡ ≤ <⎨
2.14 EXAMPLE 
Suppose the joint density of completion times for the two algorithms is given by 
( ) ( )( )
( )( )
, 1 3 4
5 8 2 4
f x y x y
α απ π
= ≤ < ≤ <
+ ≤ < ≤ <
      (19) 
Figure 7. 
,f α απ π  
Figure 8. 
,ET α απ π  
The minimum occurs at 1 3τ = . Note that if 1 3τ = , then ( )
, 1 4ET α απ π τ = , while 
4.25E απ =  and 2 4.25E απ = . In this case the derived algorithm has better mean 
execution time than either of the original algorithms. Its mean execution time is 
approximately 6%  less than that of either of the original algorithms. 
2.15 EXAMPLE 
Suppose the joint density of completion times for the two algorithms is given by 
( ) ( )
, , expf x y x yα απ π = − −
        
Figure 9. 
,f α απ π  
Figure 10. 
,ET α απ π  
Note that for any choice of 1τ , then ( )
, 1 1ET α απ π τ = , while 1 1E απ =  and 2 1E απ = . In 
this case the derived algorithm has exactly the same mean execution time as do the 
original algorithms, so a derived algorithm would be of no benefit. 
2.16 ( )
, 1ET α απ π τ  DOES NOT ALWAYS EXIST  
If we take ( )
( ) ( )1 2
f x y
x yα α
π π =
, then  
( ) ( ) ( )
1 2 1 2
, 1 ,
0 0 0
,xf x y dydx y f x y dydx
α α α α
π π π π
∞ ∞ ∞
+ + =∫ ∫ ∫ ∫     (21) 
so in this case ( )
, 1ET α απ π τ  does not exist. 
2.2 ( )
, 1ET α απ π τ  WHEN JOINT DENSITY IS OF THE FORM 
( ) ( ) (
1 2 1 2
, , )f x y f x f yα α α απ π π π=  
( ) ( ) ( )( )
( ) ( ) ( ) (
1 21 2 1
1 1 1 2 1
, 1 1 1
1 1 1 1
ET xf x dx P E
E P E P
α α α
π π π α α
α α α α α
τ τ π τ
π π τ π τ τ π τ π
= + < +
= ≤ ≤ + + <
2.3 ( )
, 1ET α απ π τ  WHEN JOINT DENSITY IS OF THE FORM 
( ) ( )
1 2 2
ax by cx dy
xpf x y x y
a b c dα απ π
+ + + +
+ + + +
If  then 0 , , ,a b c d≤ ( ) (
1 2 2
ax by cx dy )xpf x y x y
a b c dα απ π
+ + + +
= − −
+ + + +
 is a density 
function over ( ) . Accordingly, [ ) [ ), 0, 0,x y ∈ ∞ × ∞
( ) ( )
1 2 6 2 2 4 4 exp
1 2 2
a b c d c a b c d
a b c dα απ π
+ + + + − + − + − −
+ + + +
  (23) 
2.4 ( )
, 1ET α απ π τ  WHEN JOINT DENSITY IS OF THE FORM 
( ) ( )
( )( )
( ) ( )1 2
, 2 3 3
1 1 1 1
f x y d m n
x y x yα α
+ + + +
If , 0 , , then  ( )0 ,d m n≤ c≤ ( )
c d m n
+ =∑∑ 1
( ) ( )
( )( )
( ) ( )1 2
, 2 3 3
1 1 1 1
f x y d m n
x y x yα α
+ + + +
is a density function over ( ) [ ) [ ), 0, 0,x y ∈ ∞ × ∞ . A straightforward calculation yields  
( ) ( ) ( ) ( )
( ) ( ) ( )
0 2 0 01 1
1, , 0,
2 1 1 1
1 1 1
2, 1, ln 1
n m n n
ET d n d m n d
d m n d m n c
∞ ∞ ∞ ∞
= = = =
= + + +
+ + +
+ − − − +⎜ ⎟+⎝ ⎠+
∑ ∑ ∑ ∑
  (25) 
2.5 ( )
, 1ET α απ π τ  WHEN JOINT DENSITY IS OF THE FORM 
( ) ( )(
n n n n n
)f x y k a x b c y d
α απ π
= ≤ < ≤ <∑  
Theorem 2: If  and ( )( )
n n n n n
k b a d c
− −∑ = 0 nk<  for 1, 2, ,n N= , and 
( ) ( )(
n n n n n
)f x y k a x b c y d
α απ π
= ≤ < ≤ <∑ , then 
( ) ( )
( )( )
( )( )( )
( )( )
( )( )( )
( )( )
, 1 1 2
n n n
n n n n n
n n n n n n
n n n n n
n n n n n n n
n n n n n
ET k d c
k b a d c
k b d c d c
k b a d c
k b d c a d c
k b a d c
α απ π
⎜ ⎟= − −⎜ ⎟⎜ ⎟
− −⎜ ⎟
+ ⎜ ⎟
⎜ ⎟+ − + −⎜ ⎟
+ − −
+ + −
+ − −
      (26) 
Notation: In the following, if  is a Boolean expression, then . ( )B n
( )( )
s B n
≡∑ ∑ s
Proof: If  and 0( )( )
n n n n n
k b a d c
− −∑ = nk<  for 1, 2, ,n N= , then 
( ) ( )(
n n n n n
)f x y k a x b c y d
α απ π
= ≤ < ≤ <∑  is a density function over 
. Now note that ( ) [ ) [ ), 0, 0,x y ∈ ∞ × ∞
( ) ( ) ( ) ( )
1 2 1 2 1 2
, 1 , 1 ,
0 0 0
,ET xf x y dydx y f x y dydx
α α α α α α
π π π π π π
∞ ∞ ∞
= + +∫ ∫ ∫ ∫ ,      
( )( )
( ) ( )( )
n n n n n
n n n n n
x k a x b c y d dydx
y k a x b c y d dydx
= ≤ < ≤ <
+ + ≤ < ≤ <
     (27) 
( )( )
( )( )( )
( ) ( )
( ) ( )
1 0 0
n n n n n
n n n n n
n n n n n
n n n
k x a x b c y d dydx
k y a x b c y d dy
k d c x a x b dx
k a x b dx y dy
= ≤ < ≤ <
+ + ≤ < ≤ <
= − ≤ <
+ ≤ < +
∑ ∫ ∫
     (28) 
( ) ( )
( ) ( ) ( )
( ) ( )
( ) ( )
( ) ( )
( )( ) ( )
n n n n n
n n n
n n n n n
n n n n n
n n n n n
n n n n n n n
k d c x a x b dx
k a x b dx
k d c x a x b dx
k d c x a x b dx
k d c x a x b dx
k d c c d a x b dx
= − ≤ <
⎛ ⎞+ +
⎜ ⎟+ ≤ < −
= − ≤ <
+ − ≤ <
+ − ≤ <
+ − + + ≤ <
( )( ) ( )
( )( ) ( )
n n n n n n n
n n n n n n n
k d c c d a x b dx
k d c c d a x b dx
+ − + + ≤ <
+ − + + ≤ <
    (29) 
( ) ( ) ( )
( ) ( )
( )( ) ( )
( )( ) ( )
n n n n n
n n n n n
n n n n n n n
n n n n n n n
n n n n n
ET k d c x a x b dx
k d c x a x b dx
k d c c d a x b dx
k d c c d a x b dx
k d c xdx k d
= − ≤ <
+ − ≤ <
+ − + + ≤ <
+ − + + ≤ <
= − + −
∑ ∫ ( )
( )( )
( )( )
( )( ) ( ) ( )
( )( )( )
2 2 21 1 1
12 2 2
n n n
n n n n n
n n n n n
n n n n n n n n n
a b b
n n n n n n n
n n n
c xdx
k d c c d dx
k d c c d dx
k d c a k d c b a
k d c c d b a
k d c
< < ≤
+ − + +
+ − + +
= − − + −
+ − + + −
( )( )
n n n
c d b
+ + −∑
( )( )
( )( )( )
( )( )
( )( )( )
( )( )
n n n
n n n n n
n n n n n n
n n n n n
n n n n n n n
n n n n n
k d c
k b a d c
k b d c d c
k b a d c
k b d c a d c
k b a d c
⎜ ⎟= − −⎜ ⎟⎜ ⎟
− −⎜ ⎟
+ ⎜ ⎟
⎜ ⎟+ − + −⎜ ⎟
+ − −
+ + −
+ − −
       (31)
( ) ( )
( )( )
( )( )( )
( )( )
( )( )( )
( )( )
, 1 1 2
n n n
n n n n n
n n n n n n
n n n n n
n n n n n n n
n n n n n
ET k d c
k b a d c
k b d c d c
k b a d c
k b d c a d c
k b a d c
α απ π
⎜ ⎟= − −⎜ ⎟⎜ ⎟
− −⎜ ⎟
+ ⎜ ⎟
⎜ ⎟+ − + −⎜ ⎟
+ − −
+ + −
+ − −
      (32) 
In particular, 
( ) ( )
( )( )
( )( )( )
( )( )
( )( )( )
( )( )
n i n
n i n
n i n
i i n n n
a a b
n n n n n
n n n n n n
a a b
n n n n n
n n n n n n n
a a b
n n n n n
ET a a k d c
k b a d c
k b d c d c
k b a d c
k b d c a d c
k b a d c
α απ π
⎜ ⎟= − −⎜ ⎟⎜ ⎟
− −⎜ ⎟
+ ⎜ ⎟
⎜ ⎟+ − + −⎜ ⎟
+ − −
+ + −
+ − −
      (33) 
( ) ( )
( )( )
( )( )( )
( )( )
( )( )( )
( )( )
n i n
n i n
n i n
i i n n n
a b b
n n n n n
n n n n n n
a b b
n n n n n
n n n n n n n
a b b
n n n n n
ET b b k d c
k b a d c
k b d c d c
k b a d c
k b d c a d c
k b a d c
α απ π
⎜ ⎟= − −⎜ ⎟⎜ ⎟
− −⎜ ⎟
+ ⎜ ⎟
⎜ ⎟+ − + −⎜ ⎟
+ − −
+ + −
+ − −
      (34) 
It is straightforward to show that ( )
, 1ET α απ π τ  attains a global minimum at one of the 
points { }1 2 1 2, , , , ,Na a a b b bN . Indeed, ( )
, 1ET α απ π τ  is a continuous, piecewise 
quadratic function. Notice that the set of points of connection of the pieces is a subset of 
{ }1 2 1 2, , , , ,Na a a b b bN . Each piece is either linear or is quadratic with a negative 
second derivative. We can thus replace each quadratic piece with a linear piece 
connecting the endpoints of the quadratic piece, without altering the global minimum of  
, 1ET α απ π τ . After replacing each quadratic piece with the appropriate linear piece, we 
then have a continuous piecewise linear function whose global minimum is the same as 
that of ( )
, 1ET α απ π τ . But of course the global minimum of a continuous piecewise linear 
function is attained at one of its vertices. These vertices are a subset of the set of points of 
connection { }1 2 1 2, , , , ,Na a a b b bN , as desired. 
This global minimum is given by 
( ) ( ) ( )
( ) ( ) ( )
1 2 1 2 1 2
1 2 1 2 1 2
, 1 , 2 ,
, 1 , 2 ,
, , ,
, , , ,
ET a ET a ET a
ET b ET b ET b
α α α α α α
α α α α α α
π π π π π π
π π π π π π
⎪ ⎪⎩ ⎭
⎬      (35) 
This minimum can be computed in ( )2O N  time. 
MAXIMUM LIKELIHOOD ESTIMATION 
Suppose ( ) ( )(
n n n n n
)f x y k a x b c y d
α απ π
= ≤ < ≤ <∑   
with the following conditions: 
1.  for 1 , 0nk > n N≤ ≤
2.  for 1 , na b< n
n N≤ ≤
3.  for 1 , nc d< n N≤ ≤
4. The boxes  for 1[ ) [ ), ,n n n n nB a b c d≡ × n N≤ ≤ are disjoint, 
5. . ( )( )
n n n n n
k b a d c
− −∑ =
Then 
,f α απ π  is a joint density function. 
Suppose next that we have observed the performance of two equivalent algorithms α  
and β  over a (finite) sample set sΩ ⊂ Ω . That is, for each task sω∈Ω  we have 
observed the values ( )απ ω  and ( )βπ ω  representing the time that algorithms α  and β  
actually took to process the task ω . We now present a maximum-likelihood procedure to 
find the “best fitting” joint density function of the form 
( ) ( )(
n n n n n
)f x y k a x b c y d
α απ π
= ≤ < ≤ <∑ ,  
subject to the five conditions above. Let ( ) ( ) ( ){ }1 1 2 2, , , , , ,P Px y x y x y  be the data 
observed, where jx  and  are the durations required by algorithms jy α  and β  
respectively, to process j sω ∈Ω , for 1 j P≤ ≤  , with sP = Ω . Our performance function 
is defined as 
( ) ( ) ( )( ) 1 2
1 2 , 1 2
, , , , N
P P N
N m m n n m n n m n
g k k k f x y k a x b c y d k k k
α απ π
≡ = ≤ < ≤ < =∑∏ ∏ N
where 
( ) ( ) ( ) ( ){ }{ }1 1 2 2, , , , , , , ; ,j P P j j j jS x y x y x y x y a x b c y d≡ ∈ ≤ < ≤ <  
We form as usual the Lagrange multiplier equations  
( )( )1 0j j j j j
S b a d c
λ + − − =  for 1 j P≤ ≤ . We have immediately that 
( )( )
j j j j
b a d c
and recalling the constraint 
n n n n n
k b a d c
= − −∑ )  
we infer 
S Pλ λ
= − = −∑  
whence 
λ = −  
thus 
( )( )
j j j j
P b a d c
Substituting into (32), we get 
( )( )
, 1 1 2
n n n n n
ET d c
P b a d cα απ π
⎜ ⎟= − −⎜ ⎟− −⎜ ⎟
( )( )
( )( )
( )( )
( )( )( )
n n n n
n n n n n
n n n n n
n n n n n
b a d c
P b a d c
b d c d c
P b a d c
− −⎜ ⎟− −⎜ ⎟
+ ⎜ ⎟
⎜ ⎟+ − +⎜ ⎟− −⎜ ⎟
( )( )
( )( )
n n n n
n n n n n
b a d c
P b a d c
+ − −
− −∑  
( )( )
( )( )( )
n n n n n n
n n n n n
b d c a d c
P b a d c
− −∑ − −  
( )( ) ( )( )
n n n n
n n n n n
b a d c
P b a d c
− −∑ −  
( )( )
n n n n
a b n n n
n n n
P b a S
b d c
P b a
⎜ ⎟⎛ ⎞ ⎜ ⎟⎜ ⎟= − + ⎜ ⎟⎜ ⎟− ⎜ ⎟⎜ ⎟ + −⎝ ⎠ ⎜ ⎟−⎜ ⎟
( )( ) ( )
1 1 1
21 1 1
2 2 2
1 1 1
n n n n
N N N
n n n n n n n n
n n nn n
a a b b
d c b d c a b a
P P b a P
τ τ τ
= = =
≤ < < ≤
+ + + + − +
∑ ∑ ∑ n
1 1 1
, 1 1 12
1 1 1
n n n n n
N N N
n n nn
n n nn n n n
a b a a b
b d cS
ET S S
b a P b aα απ π
τ τ τ
τ τ τ
= = =
< < ≤ < <
− +⎜ ⎟= − + +⎜ ⎟− −⎜ ⎟
∑ ∑ ∑  
( )( ) ( ) ( )
2 2 2
n n n n
n n n n n n n n n nP P
n nn n
a b a b
b d c a S d c S b a
< < ≤ ≤
+ + − + + +
3 CONCLUSIONS 
In this paper, we asked the following questions: Given two or more equivalent 
algorithms, is it ever possible to create a new derived algorithm whose mean execution 
time is less than that of all of the original algorithms? If so, how can such an algorithm be 
derived? 
By giving examples in Section 2, we have shown that the answer to the first question is 
“yes.” In Section 1, we gave an explicit construction of the derived algorithm. 

  In this paper we give a definition of "algorithm," "finite algorithm,"
"equivalent algorithms," and what it means for a single algorithm to dominate a
set of algorithms. We define a derived algorithm which may have a smaller mean
execution time than any of its component algorithms. We give an explicit
expression for the mean execution time (when it exists) of the derived
algorithm. We give several illustrative examples of derived algorithms with two
component algorithms. We include mean execution time solutions for
two-algorithm processors whose joint density of execution times are of several
general forms. For the case in which the joint density for a two-algorithm
processor is a step function, we give a maximum-likelihood estimation scheme
with which to analyze empirical processing time data.

COMBINING SEVERAL ALGORITHMS INTO A SUPERIOR ONE
OPTIMAL SYNTHESIS OF MULTIPLE ALGORITHMS 
KERRY M. SOILEAU 
ksoileau@yahoo.com
JULY 27, 2004 
ABSTRACT 
In this paper we give a definition of “algorithm,” “finite algorithm,” “equivalent algorithms,” and what it means for a 
single algorithm to dominate a set of algorithms. We define a derived algorithm which may have a smaller mean 
execution time than any of its component algorithms. We give an explicit expression for the mean execution time 
(when it exists) of the derived algorithm. We give several illustrative examples of derived algorithms with two 
component algorithms. We include mean execution time solutions for two-algorithm processors whose joint density of 
execution times are of several general forms. For the case in which the joint density for a two-algorithm processor is a 
step function, we give a maximum-likelihood estimation scheme with which to analyze empirical processing time data. 
mailto:ksoileau@yahoo.com
1 INTRODUCTION 
It can categorically be said that no algorithm is unique. By this we mean that for a given 
task, invariably more than one algorithm exists which will accomplish that task. One 
strategy is to select one algorithm deemed generally superior to the rest, and to use that 
algorithm exclusively. This paper examines an alternative strategy. We ask, given two or 
more equivalent algorithms, is it ever possible to create a new derived algorithm whose 
mean execution time is less than that of all of the original algorithms? If so, how can such 
an algorithm be derived? 
First we define clearly what we mean by the term “algorithm:”  
Algorithm: An algorithm α  is a pair ( ),α αρ π , where :αρ Ω→Γ  is a Turing-
computable mapping of a countable set Ω  (tasks) into a countable set Γ  (outputs), and 
:απ Ω→  is a mapping of  into the positive real numbers. The function Ω αρ  specifies 
the algorithm’s output ( )αρ ω  when presented with the task ω∈Ω . The function απ  
specifies the execution time ( )απ ω  required to compute the output ( )αρ ω . Note that 
under this definition, given a task ω∈Ω , an algorithm will always produce a definite 
output, namely ( )αρ ω , and will always produce this output after a definite amount of 
time has passed, namely ( )απ ω . We do not address procedures which are 
nondeterministic or whose execution time is unpredictable. 
Definition: We say that an algorithm ( ),α αα ρ π=  is finite if and only if  
for every 
( )0 απ ω< < ∞
ω∈Ω . Note that “ ( ),α αα ρ π=  is finite” does not imply “ απ  is bounded.” For 
example, Quicksort and Bubblesort are finite. 
Definition: We say that two algorithms ( ),α αα ρ π=  and ( ),β ββ ρ π=  are equivalent if 
and only if Dom Dom α βρ ρ=  and ( ) ( )α βρ ω ρ ω=  for every ω∈Ω . Notice that 
equivalent algorithms may require different times to process a given task. For example, 
Quicksort and Bubblesort are equivalent. 
Definition: Let { }1 2, , , Nα α α  be a set of equivalent algorithms. We say that nα  
dominates { }1 2, , , Nα α α  if and only if for every ω∈Ω , ( ) (n iα α )π ω π ω≤  for every 
{ }1,2, ,i N∈ . 
Now suppose we are given a set of finite equivalent algorithms { }1 2, , , Nα α α  such that 
no nα  dominates { }1 2, , , Nα α α . Suppose further that there exists a probability space 
 over  such that ( ), , PΩ ℑ Ω
, , ,
Nα α α
π π π  are random variables. Let 
 be the joint density of the random variables 
, , , :
α α απ π π
, , ,
Nα α α
π π π . 
Definition of Derived Algorithm: From a set of finite equivalent algorithms 
{ }1 2, , , Nα α α , and a given point ( ) [ )
1 2 1, , , 0,
Nτ τ τ
− ∈ ∞ , the function 
 is defined as follows. For each 
, we define the random variable 
1 2 11 2 1
| | | :
NN Nτ τ τ
α α α α
⎡ Ω→ Γ⎣ ⎤⎦
( ) [ ) 11 2 1, , , 0,
Nτ τ τ
− ∈ ∞
, , , 1 2 1, , , :
NT α α απ π π τ τ τ − Ω→  
as follows: 
( )( )
, , , 1 2 1
1 2 2 3
1 2 2 2
1 2 1 1
, , ,
α α απ π π
τ τ τ ω
π ω ω
τ π ω ω
τ τ π ω ω
τ τ τ π ω ω
τ τ τ π ω ω
⎪ + + ∈⎪
⎪ + + + + ∈
⎪ + + + + ∈⎩
     (1) 
1 2 1
1 2 1
| | |
τ τ τ
ρ ω ω
ρ ω ω
ρ ω ω
α α α α ω
ρ ω ω
ρ ω ω
⎪ ∈⎪⎡ ⎤ = ⎨⎣ ⎦
   (2) 
where ( ) ( ) ( ){ }
1 21 2
; , , ,
S α α αω τ π ω τ π ω τ π ω= ∈Ω < < <  for 1 1n N≤ ≤ − . Each  
is the event consisting of the points 
ω∈Ω  on which none of the algorithms 1 2, , , nα α α  
completes processing within each algorithm’s permitted run time limit. The derived 
algorithm is then defined to be the pair 
.  ( )( )1 2 1 1 21 2 1 , , , 1 2 1| | | , , , ,N NN N NT α α ατ τ τ π π πα α α α τ τ τ−− −⎡ ⎤⎣ ⎦
( )( )
, , , 1 2 1, , ,
NT α α απ π π τ τ τ ω−  represents the time taken for the derived algorithm to 
execute when presented with the task ω , and 
1 2 11 2 1
| | |
NNτ τ τ N
α α α α
⎡ ⎤⎣ ⎦  represents the 
derived algorithm’s output when presented with the task ω .  
We may envision an implementation of this algorithm as follows. When presented with a 
task ω∈Ω , a timer is started, and 1α  is applied. If 1α  has not completed by time 1τ , 1α  
is abandoned and 2α  is applied. If 2α  has not completed by time 1 2τ τ+ , 2α  is 
abandoned and 3α  is applied, and so on. If 1Nα −  has not completed by time 
1 2 1Nτ τ τ −+ + + 1N, α −  is abandoned and Nα  is applied and (unlike the other algorithms) 
is allowed to run without time limit. ( )
ρ ω  is returned as output , where iα  is the 
algorithm which completed execution on the task ω∈Ω . 
The expected value (if it exists) of the random variable ( )
, , , 1 2 1, , ,
NT α α απ π π τ τ τ −  is 
given by the following  
Theorem 1: 
( ) ( ) ( )
( ) ( ) ( ) ( )
, , , 1 2 1 1 1
1 1 1
, , ,
n n n n N N
ET E S P S
E S S P S S E S P S
α α απ π π α
τ τ τ π
− − −
= Ω Ω
∼ ∼ 1−
Proof: Recall that 
( )( )
, , , 1 2 1
1 2 2 3
1 2 2 2
1 2 1 1
, , ,
α α απ π π
τ τ τ ω
π ω ω
τ π ω ω
τ τ π ω ω
τ τ τ π ω ω
τ τ τ π ω ω
⎪ + + ∈⎪
⎪ + + + + ∈
⎪ + + + + ∈⎩
It follows immediately that 
( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
, , , 1 2 1
1 1 2 1 2
1 2 2 3 2 3
1 2 2 2 1 2 1
1 2 1 1 1
, , ,
N N N N
N N N
E S P S
E S S P S S
E S S P S S
E S S P
E S P S
α α απ π π
τ τ τ
τ τ π
τ τ τ π
τ τ τ π
− − − −
− − −
= Ω Ω
+ + +
+ + + + +
+ + + + +
∼ NS S −∼
    (4) 
This may be written as  
 ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( ) ( ) ( )
, , , 1 2 1 1 1 1 1 2
1 2 1 2 1 2 2 3
2 3 2 3
1 2 2 2 1
2 1 2 1
1 2 1 1 1 1
, , ,
N N N
N N N N
N N N N
ET E S P S P S S
E S S P S S P S S
E S S P S S
P S S
E S S P S S
P S E S P S
α α απ π π α
τ τ τ π τ
π τ τ
τ τ τ
τ τ τ π
− − −
− − − −
− − − −
= Ω Ω +
+ + +
+ + + + +
+ + + + +
∼ ∼ ∼
∼ ∼ ∼
∼ ∼   
Telescoping sums yield
 ( ) ( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( ) ( ) ( )( )
( ) ( ) ( )( ) ( )( )
, , , 1 2 1 1 1
1 2 1 2
2 3 2 3
2 1 2 1
1 1 2 2 3 2 1 1
2 2 3 2 1 1 1 1
, , ,
N N N N
N N N
N N N N N
ET E S P S
E S S P S S
E S S P S S
E S S P S S
E S P S
P S S P S S P S S P S
P S S P S S P S P S
α α απ π π α
τ τ τ π
− − − −
− − −
− − − − −
= Ω Ω
+ + + + +
+ + + + + +
∼ ∼ ∼
Next,
( ) ( ) ( )
( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( )
, , , 1 2 1 1 1
1 2 1 2
2 3 2 3 2 1 2 1
1 1 1 1 2 2 1 1
, , ,
N N N N
N N N N
ET E S P S
E S S P S S
E S S P S S E S S P S S
E S P S P S P S P S
α α απ π π α
τ τ τ π
π τ τ τ
− − −
− − − −
= Ω Ω
+ + +
+ + + + +
∼ ∼ ∼ ∼ −
whence 
( ) ( ) ( )
( ) ( ) ( ) ( ) (
, , , 1 2 1 1 1
1 1 1 1
, , ,
n n n n N N n
ET E S P S
)nE S S P S S E S P S P S
α α απ π π α
τ τ τ π
− − − −
= Ω Ω
+ +∑ ∑
∼ ∼ τ+
as desired.
2 CASE  (TWO ALGORITHMS) 2N =
In this case 
( )( )
( ) ( )
( ) ( )
π ω π ω
τ π ω τ π ω
+ <⎪⎩       
( ) ( ) ( ) ( ) ( ) ( )
1 21 2
, 1 1 1 1 1 1 1ET E S P S E S P S P Sα απ π α ατ π π τ= Ω Ω + +∼ ∼
 and 
( ){ }
;S αω τ π ω= ∈Ω < ,        (11) 
( ) ( ) ( ) ( )( ) ( )1 1 1 2 1 11 2, 1 1 1 1 1 1ET E P E Pα απ π α α α α α ατ π π τ π τ π τ π τ τ π= ≤ ≤ + < + <  (12) 
2.1 ( )
, 1ET α απ π τ  WHEN JOINT DENSITY IS ( )1 2, ,f x yα απ π  
In this case, 
( ) ( ) ( ) ( )
1 2 1 2 1 2
, 1 , 1 ,
0 0 0
,ET xf x y dydx y f x y dydx
α α α α α α
π π π π π π
∞ ∞ ∞
= + +∫ ∫ ∫ ∫ ,    (13) 
2.11 EXAMPLE 
Suppose the joint density of completion times for the two algorithms is given by 
( ) ( )(
, , 12 exp )f x y xy x yα απ π = − +        (14) 
Figure 1. 
,f α απ π  
Then 
( ) ( )( )( ) ( ) ( )
4 2 3 23 3
, 1 1 1 1 1 1 12 8erf 1 expET α απ π τ π τ τ τ τ τ τ= − + + + − + π   (15) 
Figure 2. 
,ET α απ π  
2.12 EXAMPLE 
Suppose the joint density of completion times for the two algorithms is given by 
( ) ( )
, , 48 exp 4 3f x y xy x yα απ π = − −
       
Figure 3. 
,f α απ π  
Then 
( ) ( ) ( )
, 1 1 14 6erf 2 3 exp 4ET α απ π τ π τ π τ= + −      (17) 
Figure 4. 
,ET α απ π  
2.13 EXAMPLE 
Suppose the joint density of completion times for the two algorithms is given by 
( ) ( )( )
( ) ( )( )1 2
, 2 2
exp 1 7
, .022179119694367830844
exp 7 1
f x y xy
α απ π
⎛ ⎞− − − −
⎜ ⎟= ⎜ ⎟
+ − − − −⎜ ⎟
   (18) 
Figure 5. 
,f α απ π  
Figure 6. 
,ET α απ π  
The minimum occurs at 1 2.492τ . Note that if 1 2.492τ , then ( )
, 1 2.854ET α απ π τ , 
while 
4.260E απ  and 2 4.260E απ . In this case the derived algorithm has better mean 
execution time than either of the original algorithms. Its mean execution time is 
approximately 33% less than that of either of the original algorithms. 
Notation: In the following, wherever 1 2, , , MB B B  is found in a context requiring a 
Boolean expression, it means the conjunction 1 2 MB B B∧ ∧ ∧  of the Boolean 
expressions 1 2, , , MB B B .
Notation: In the following, if B  is a Boolean expression, then ( ) .  
1  is tru
0  is fals
In particular we define ( )
a x b a x x b
≤ < ≡ ≤ <⎨
2.14 EXAMPLE 
Suppose the joint density of completion times for the two algorithms is given by 
( ) ( )( )
( )( )
, 1 3 4
5 8 2 4
f x y x y
α απ π
= ≤ < ≤ <
+ ≤ < ≤ <
      (19) 
Figure 7. 
,f α απ π  
Figure 8. 
,ET α απ π  
The minimum occurs at 1 3τ = . Note that if 1 3τ = , then ( )
, 1 4ET α απ π τ = , while 
4.25E απ =  and 2 4.25E απ = . In this case the derived algorithm has better mean 
execution time than either of the original algorithms. Its mean execution time is 
approximately 6%  less than that of either of the original algorithms. 
2.15 EXAMPLE 
Suppose the joint density of completion times for the two algorithms is given by 
( ) ( )
, , expf x y x yα απ π = − −
        
Figure 9. 
,f α απ π  
Figure 10. 
,ET α απ π  
Note that for any choice of 1τ , then ( )
, 1 1ET α απ π τ = , while 1 1E απ =  and 2 1E απ = . In 
this case the derived algorithm has exactly the same mean execution time as do the 
original algorithms, so a derived algorithm would be of no benefit. 
2.16 ( )
, 1ET α απ π τ  DOES NOT ALWAYS EXIST  
If we take ( )
( ) ( )1 2
f x y
x yα α
π π =
, then  
( ) ( ) ( )
1 2 1 2
, 1 ,
0 0 0
,xf x y dydx y f x y dydx
α α α α
π π π π
∞ ∞ ∞
+ + =∫ ∫ ∫ ∫     (21) 
so in this case ( )
, 1ET α απ π τ  does not exist. 
2.2 ( )
, 1ET α απ π τ  WHEN JOINT DENSITY IS OF THE FORM 
( ) ( ) (
1 2 1 2
, , )f x y f x f yα α α απ π π π=  
( ) ( ) ( )( )
( ) ( ) ( ) (
1 21 2 1
1 1 1 2 1
, 1 1 1
1 1 1 1
ET xf x dx P E
E P E P
α α α
π π π α α
α α α α α
τ τ π τ
π π τ π τ τ π τ π
= + < +
= ≤ ≤ + + <
2.3 ( )
, 1ET α απ π τ  WHEN JOINT DENSITY IS OF THE FORM 
( ) ( )
1 2 2
ax by cx dy
xpf x y x y
a b c dα απ π
+ + + +
+ + + +
If  then 0 , , ,a b c d≤ ( ) (
1 2 2
ax by cx dy )xpf x y x y
a b c dα απ π
+ + + +
= − −
+ + + +
 is a density 
function over ( ) . Accordingly, [ ) [ ), 0, 0,x y ∈ ∞ × ∞
( ) ( )
1 2 6 2 2 4 4 exp
1 2 2
a b c d c a b c d
a b c dα απ π
+ + + + − + − + − −
+ + + +
  (23) 
2.4 ( )
, 1ET α απ π τ  WHEN JOINT DENSITY IS OF THE FORM 
( ) ( )
( )( )
( ) ( )1 2
, 2 3 3
1 1 1 1
f x y d m n
x y x yα α
+ + + +
If , 0 , , then  ( )0 ,d m n≤ c≤ ( )
c d m n
+ =∑∑ 1
( ) ( )
( )( )
( ) ( )1 2
, 2 3 3
1 1 1 1
f x y d m n
x y x yα α
+ + + +
is a density function over ( ) [ ) [ ), 0, 0,x y ∈ ∞ × ∞ . A straightforward calculation yields  
( ) ( ) ( ) ( )
( ) ( ) ( )
0 2 0 01 1
1, , 0,
2 1 1 1
1 1 1
2, 1, ln 1
n m n n
ET d n d m n d
d m n d m n c
∞ ∞ ∞ ∞
= = = =
= + + +
+ + +
+ − − − +⎜ ⎟+⎝ ⎠+
∑ ∑ ∑ ∑
  (25) 
2.5 ( )
, 1ET α απ π τ  WHEN JOINT DENSITY IS OF THE FORM 
( ) ( )(
n n n n n
)f x y k a x b c y d
α απ π
= ≤ < ≤ <∑  
Theorem 2: If  and ( )( )
n n n n n
k b a d c
− −∑ = 0 nk<  for 1, 2, ,n N= , and 
( ) ( )(
n n n n n
)f x y k a x b c y d
α απ π
= ≤ < ≤ <∑ , then 
( ) ( )
( )( )
( )( )( )
( )( )
( )( )( )
( )( )
, 1 1 2
n n n
n n n n n
n n n n n n
n n n n n
n n n n n n n
n n n n n
ET k d c
k b a d c
k b d c d c
k b a d c
k b d c a d c
k b a d c
α απ π
⎜ ⎟= − −⎜ ⎟⎜ ⎟
− −⎜ ⎟
+ ⎜ ⎟
⎜ ⎟+ − + −⎜ ⎟
+ − −
+ + −
+ − −
      (26) 
Notation: In the following, if  is a Boolean expression, then . ( )B n
( )( )
s B n
≡∑ ∑ s
Proof: If  and 0( )( )
n n n n n
k b a d c
− −∑ = nk<  for 1, 2, ,n N= , then 
( ) ( )(
n n n n n
)f x y k a x b c y d
α απ π
= ≤ < ≤ <∑  is a density function over 
. Now note that ( ) [ ) [ ), 0, 0,x y ∈ ∞ × ∞
( ) ( ) ( ) ( )
1 2 1 2 1 2
, 1 , 1 ,
0 0 0
,ET xf x y dydx y f x y dydx
α α α α α α
π π π π π π
∞ ∞ ∞
= + +∫ ∫ ∫ ∫ ,      
( )( )
( ) ( )( )
n n n n n
n n n n n
x k a x b c y d dydx
y k a x b c y d dydx
= ≤ < ≤ <
+ + ≤ < ≤ <
     (27) 
( )( )
( )( )( )
( ) ( )
( ) ( )
1 0 0
n n n n n
n n n n n
n n n n n
n n n
k x a x b c y d dydx
k y a x b c y d dy
k d c x a x b dx
k a x b dx y dy
= ≤ < ≤ <
+ + ≤ < ≤ <
= − ≤ <
+ ≤ < +
∑ ∫ ∫
     (28) 
( ) ( )
( ) ( ) ( )
( ) ( )
( ) ( )
( ) ( )
( )( ) ( )
n n n n n
n n n
n n n n n
n n n n n
n n n n n
n n n n n n n
k d c x a x b dx
k a x b dx
k d c x a x b dx
k d c x a x b dx
k d c x a x b dx
k d c c d a x b dx
= − ≤ <
⎛ ⎞+ +
⎜ ⎟+ ≤ < −
= − ≤ <
+ − ≤ <
+ − ≤ <
+ − + + ≤ <
( )( ) ( )
( )( ) ( )
n n n n n n n
n n n n n n n
k d c c d a x b dx
k d c c d a x b dx
+ − + + ≤ <
+ − + + ≤ <
    (29) 
( ) ( ) ( )
( ) ( )
( )( ) ( )
( )( ) ( )
n n n n n
n n n n n
n n n n n n n
n n n n n n n
n n n n n
ET k d c x a x b dx
k d c x a x b dx
k d c c d a x b dx
k d c c d a x b dx
k d c xdx k d
= − ≤ <
+ − ≤ <
+ − + + ≤ <
+ − + + ≤ <
= − + −
∑ ∫ ( )
( )( )
( )( )
( )( ) ( ) ( )
( )( )( )
2 2 21 1 1
12 2 2
n n n
n n n n n
n n n n n
n n n n n n n n n
a b b
n n n n n n n
n n n
c xdx
k d c c d dx
k d c c d dx
k d c a k d c b a
k d c c d b a
k d c
< < ≤
+ − + +
+ − + +
= − − + −
+ − + + −
( )( )
n n n
c d b
+ + −∑
( )( )
( )( )( )
( )( )
( )( )( )
( )( )
n n n
n n n n n
n n n n n n
n n n n n
n n n n n n n
n n n n n
k d c
k b a d c
k b d c d c
k b a d c
k b d c a d c
k b a d c
⎜ ⎟= − −⎜ ⎟⎜ ⎟
− −⎜ ⎟
+ ⎜ ⎟
⎜ ⎟+ − + −⎜ ⎟
+ − −
+ + −
+ − −
       (31)
( ) ( )
( )( )
( )( )( )
( )( )
( )( )( )
( )( )
, 1 1 2
n n n
n n n n n
n n n n n n
n n n n n
n n n n n n n
n n n n n
ET k d c
k b a d c
k b d c d c
k b a d c
k b d c a d c
k b a d c
α απ π
⎜ ⎟= − −⎜ ⎟⎜ ⎟
− −⎜ ⎟
+ ⎜ ⎟
⎜ ⎟+ − + −⎜ ⎟
+ − −
+ + −
+ − −
      (32) 
In particular, 
( ) ( )
( )( )
( )( )( )
( )( )
( )( )( )
( )( )
n i n
n i n
n i n
i i n n n
a a b
n n n n n
n n n n n n
a a b
n n n n n
n n n n n n n
a a b
n n n n n
ET a a k d c
k b a d c
k b d c d c
k b a d c
k b d c a d c
k b a d c
α απ π
⎜ ⎟= − −⎜ ⎟⎜ ⎟
− −⎜ ⎟
+ ⎜ ⎟
⎜ ⎟+ − + −⎜ ⎟
+ − −
+ + −
+ − −
      (33) 
( ) ( )
( )( )
( )( )( )
( )( )
( )( )( )
( )( )
n i n
n i n
n i n
i i n n n
a b b
n n n n n
n n n n n n
a b b
n n n n n
n n n n n n n
a b b
n n n n n
ET b b k d c
k b a d c
k b d c d c
k b a d c
k b d c a d c
k b a d c
α απ π
⎜ ⎟= − −⎜ ⎟⎜ ⎟
− −⎜ ⎟
+ ⎜ ⎟
⎜ ⎟+ − + −⎜ ⎟
+ − −
+ + −
+ − −
      (34) 
It is straightforward to show that ( )
, 1ET α απ π τ  attains a global minimum at one of the 
points { }1 2 1 2, , , , ,Na a a b b bN . Indeed, ( )
, 1ET α απ π τ  is a continuous, piecewise 
quadratic function. Notice that the set of points of connection of the pieces is a subset of 
{ }1 2 1 2, , , , ,Na a a b b bN . Each piece is either linear or is quadratic with a negative 
second derivative. We can thus replace each quadratic piece with a linear piece 
connecting the endpoints of the quadratic piece, without altering the global minimum of  
, 1ET α απ π τ . After replacing each quadratic piece with the appropriate linear piece, we 
then have a continuous piecewise linear function whose global minimum is the same as 
that of ( )
, 1ET α απ π τ . But of course the global minimum of a continuous piecewise linear 
function is attained at one of its vertices. These vertices are a subset of the set of points of 
connection { }1 2 1 2, , , , ,Na a a b b bN , as desired. 
This global minimum is given by 
( ) ( ) ( )
( ) ( ) ( )
1 2 1 2 1 2
1 2 1 2 1 2
, 1 , 2 ,
, 1 , 2 ,
, , ,
, , , ,
ET a ET a ET a
ET b ET b ET b
α α α α α α
α α α α α α
π π π π π π
π π π π π π
⎪ ⎪⎩ ⎭
⎬      (35) 
This minimum can be computed in ( )2O N  time. 
MAXIMUM LIKELIHOOD ESTIMATION 
Suppose ( ) ( )(
n n n n n
)f x y k a x b c y d
α απ π
= ≤ < ≤ <∑   
with the following conditions: 
1.  for 1 , 0nk > n N≤ ≤
2.  for 1 , na b< n
n N≤ ≤
3.  for 1 , nc d< n N≤ ≤
4. The boxes  for 1[ ) [ ), ,n n n n nB a b c d≡ × n N≤ ≤ are disjoint, 
5. . ( )( )
n n n n n
k b a d c
− −∑ =
Then 
,f α απ π  is a joint density function. 
Suppose next that we have observed the performance of two equivalent algorithms α  
and β  over a (finite) sample set sΩ ⊂ Ω . That is, for each task sω∈Ω  we have 
observed the values ( )απ ω  and ( )βπ ω  representing the time that algorithms α  and β  
actually took to process the task ω . We now present a maximum-likelihood procedure to 
find the “best fitting” joint density function of the form 
( ) ( )(
n n n n n
)f x y k a x b c y d
α απ π
= ≤ < ≤ <∑ ,  
subject to the five conditions above. Let ( ) ( ) ( ){ }1 1 2 2, , , , , ,P Px y x y x y  be the data 
observed, where jx  and  are the durations required by algorithms jy α  and β  
respectively, to process j sω ∈Ω , for 1 j P≤ ≤  , with sP = Ω . Our performance function 
is defined as 
( ) ( ) ( )( ) 1 2
1 2 , 1 2
, , , , N
P P N
N m m n n m n n m n
g k k k f x y k a x b c y d k k k
α απ π
≡ = ≤ < ≤ < =∑∏ ∏ N
where 
( ) ( ) ( ) ( ){ }{ }1 1 2 2, , , , , , , ; ,j P P j j j jS x y x y x y x y a x b c y d≡ ∈ ≤ < ≤ <  
We form as usual the Lagrange multiplier equations  
( )( )1 0j j j j j
S b a d c
λ + − − =  for 1 j P≤ ≤ . We have immediately that 
( )( )
j j j j
b a d c
and recalling the constraint 
n n n n n
k b a d c
= − −∑ )  
we infer 
S Pλ λ
= − = −∑  
whence 
λ = −  
thus 
( )( )
j j j j
P b a d c
Substituting into (32), we get 
( )( )
, 1 1 2
n n n n n
ET d c
P b a d cα απ π
⎜ ⎟= − −⎜ ⎟− −⎜ ⎟
( )( )
( )( )
( )( )
( )( )( )
n n n n
n n n n n
n n n n n
n n n n n
b a d c
P b a d c
b d c d c
P b a d c
− −⎜ ⎟− −⎜ ⎟
+ ⎜ ⎟
⎜ ⎟+ − +⎜ ⎟− −⎜ ⎟
( )( )
( )( )
n n n n
n n n n n
b a d c
P b a d c
+ − −
− −∑  
( )( )
( )( )( )
n n n n n n
n n n n n
b d c a d c
P b a d c
− −∑ − −  
( )( ) ( )( )
n n n n
n n n n n
b a d c
P b a d c
− −∑ −  
( )( )
n n n n
a b n n n
n n n
P b a S
b d c
P b a
⎜ ⎟⎛ ⎞ ⎜ ⎟⎜ ⎟= − + ⎜ ⎟⎜ ⎟− ⎜ ⎟⎜ ⎟ + −⎝ ⎠ ⎜ ⎟−⎜ ⎟
( )( ) ( )
1 1 1
21 1 1
2 2 2
1 1 1
n n n n
N N N
n n n n n n n n
n n nn n
a a b b
d c b d c a b a
P P b a P
τ τ τ
= = =
≤ < < ≤
+ + + + − +
∑ ∑ ∑ n
1 1 1
, 1 1 12
1 1 1
n n n n n
N N N
n n nn
n n nn n n n
a b a a b
b d cS
ET S S
b a P b aα απ π
τ τ τ
τ τ τ
= = =
< < ≤ < <
− +⎜ ⎟= − + +⎜ ⎟− −⎜ ⎟
∑ ∑ ∑  
( )( ) ( ) ( )
2 2 2
n n n n
n n n n n n n n n nP P
n nn n
a b a b
b d c a S d c S b a
< < ≤ ≤
+ + − + + +
3 CONCLUSIONS 
In this paper, we asked the following questions: Given two or more equivalent 
algorithms, is it ever possible to create a new derived algorithm whose mean execution 
time is less than that of all of the original algorithms? If so, how can such an algorithm be 
derived? 
By giving examples in Section 2, we have shown that the answer to the first question is 
“yes.” In Section 1, we gave an explicit construction of the derived algorithm. 
