Suppose you have a roster from a census return with N entries in alphabetical order by first name. Each page has P entries.

Using the given variable

1. What is the lower bound Bl and the upper bound Bu on the number of pages that must be examined to find a given first name using a binary search? Assume that having computed a page number, you can open directly to that page.

2. Now suppose a 1-page table of contents is added to the roster. It lists the first "first name" on each of the other pages (Assume no first name has more than 1 page of entries). How many pages that must be examined to look up a given first name?

3. Now suppose that the roster is reorganized such that each page contains a list of names with the same initials. For example, 'Thomas Jam Andrew' falls on the same page as 'Travis Jam Anand' (both have initials 'TJA'). Assume that no pattern takes more than one page, and there are a total of M pages. Finally, assume that given the pattern you can go directly to the page. How many pages must be checked to find a particular name?

4. Using the same organization as question 3, assuming a page still has room for up to P entries, what is the occupancy percentage of an average page in the new roster?

5. Now suppose we add a two-level index to the roster. The one-page primary index lists the first name on each of the secondary index pages. The secondary index pages list the first name on each of the roster pages. Assume no first name has more than 1 page of entries. How many pages must be examined to look up a given first name?

Someone please help with this