Discrete Mathematics for Computer Science

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 op-

erations 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 obvi-
ous 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 al-
gorithm, 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 <AandC<B) then


2. if(A <B) then /C<A <B, so!


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 <C) then /B <A<C, so/


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