Analysis of sequential search


  1. read n, the number of entries in the phone book
  2. read N1 ,..., Nn,T1 ,..., Tn
  3. read NAME
  4. set i <- 1
  5. set found = false
  6. repeat until either found or i > n
  7.    if NAME=Ni then
  8.       write Ti
  9.        set found <- true
  10.     else
  11.       set i <- i +1
  12. // end until
  13. if not found then
  14.    write 'sorry, but the name is not in the directory' // end if
  15. stop

We simplify our task by counting only the number of comparisons performed in the sequential search (Step 7).

The worst-case number of comparisons is

TSequential_Search(n) = n.

This occurs when Name is last in the phone book or does not occur in the phone book.

The best case number of comparisons is 1, if NAME is first in the phone book.

If NAME is in the phone book, then the average number of comparisons is n/2.



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