Suppose a phone book contains 500 pages, and each page can contain up to 500 records. Suppose we want to search for a particular name in the book. Give a worst-case bound on the number of pages that must be looked at to perform a search using each of the following methods:

(i) linear search, as if the book were organized as a heap file,
(ii) binary search, using the fact that the book is ordered by names,
(iii) with an index for the name of the rst entry on each page.

500, 9 (=log2500e), 2 (the index has 500 pages, so the entire index fits in one page; so 1 access to the index and 1 to the data).