BT&T company has 256 million customers. Their current telephone directory consists of many heavy volumes typeset in small point size, which are expensive to print and inconvenient to use. To overcome the above problems, BT&T has decided to set up an on-line computerized directory, and their software engineers are debating what is the most efficient data structure for the purpose. Assume that the BT&T computer can compare two names in one microsecond. You do not need to simplify your calculations.

a) One of the engineers suggests implementing the on-line directory as an unsorted linked list. With this implementation, give an estimate of the worst-case search and insertion times.

b) Another engineer wants to implement the on-line directory as a red-black tree. With this implementation, give an estimate of the worst-case search and insertion times.

c) A third engineer proposes the use of a sorted array. With this implementation, give an estimate of the worst-case search and insertion times