Suppose that a dynamic set \(S\) is represented by a direct-address table \(T\) of length \(m\). Describe a procedure that finds the maximum element of \(S\). What is the worst-case performance of your procedure?

FIND-MAXIMUM(S)

1 max = NIL

2 for i = 0 to m-1:

3     val=DIRECT-ADDRESS-SEARCH(T, i)

4     if val > max:

5         max = val

6 return max

We must examine \(m\) distinct values because any key of \(T\) may contain the maximum. Therefore this procedure runs in \(O(m)\) time in the worst case.