THE "COUNT"
of Find Largest

 

  1. read n // the size of the list
  2. read A1, A2, ..., An
  3. set largest_so_far <- A1
  4. set location <- 1
  5. set i <- 2
  6. While i < n do
  7.     if Ai > largest_so_far then
  8.       set largest_so_far <- Ai
  9.       set location <- i // end if
  10.     i <- i + 1 // end while
  11. write largest_so_far, location
  12. stop

Worst case occurs when the input sequence is in increasing order (so that the largest is last).

Best case occurs when A1 is the largest. Then the number of steps is

3(n - 1) + 7 = 3n + 4.

The average case is

4(n - 1) + 7 = 4n + 3

though we are very lucky that this can be argued fairly simply.

There is a problem with this example, in that step 2 should count as roughly n regular steps. But this does not matter when we get to

asymptotic analysis.

[Prev][TOC][Next]

CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000