Homework 18
Due : 9.30am, 7 August
Exercise 3 from Chapter 9 of the textbook (p.434)
Solution
Consider the following trace of numbers of comparisons generated
by the algorithm for different values of J:
| J | for statement | while statement | array element comparison |
|---|
| 0 | 1 | 2 | 1 |
| 1 | 1 | 3 | 2 |
| 2 | 1 | 4 | 3 |
| 3 | 1 | 5 | 4 |
| . | . | . | . |
| N-2 | 1 | N | N-1 |
| N-1 | 1 | N+1 | N |
| in general: | 1 | J+2 | J+1 |
|---|
Plus, there is one comparison for the outer loop when the algorithm
terminates by the for statement failing.
So, the total number of comparisons is:
Last updated : 7 August 2000 8.56pm