Complexity of Programs
303
Complexity of Selection
Let n E N. Let a step of an algorithm be to make a selection for execution of one of
n blocks, B 1 , B 2 ... , Bn, and, on input I, where each Bi executes the key operations
at most Fi (Bi) times for 1 < i < n and it then takes G(I) executions of the key operations to make the selection of the block to execute. Then, the key operations are
executed at most
G(I) +-max{Fi(Bl), F 2 (B 2 ).
Fn (Bn)}
times.
The next algorithm also sorts a three-element list. To some people, it is more obvious than the preceding algorithm, since it breaks the algorithm down into the six possible
cases, asking first which element is least. For easy reference to individual lines of the algorithm, we put line numbers on the left ends of the lines. We assume the procedure Swap
interchanges the values of the two elements that are in the storage locations named by its
arguments.
INPUT: Distinct values for three variables A, B, and C
OUTPUT: The list of values in increasing order
1. if(C 2.
if(A /*C 3.
Swap(A, B)
4.
Swap(A, C)
5.
else
/* C < B < A, so*/
6.
Swap (C, A)
7. else
8.
if(B < A and B < C) then
9.
if(A /*B 10.
Swap (A, B)
11.
else
/* B < C < A, so*/
12.
Swap (A, B)
13.
Swap (B, C)
14.
else
15.
if (C < B) then
/* A < C < B, so*/
16.
Swap (B, C)
17. print A, B, C
This algorithm nests selections within selections within selections. The outermost
selection is in line 1, with its corresponding false range beginning at line 6. We will