A company database has 10,000 customers sorted by last name, 20% of whom are known to be good customers. When looking up a customer’s record in the database, the good customers account for 60%.
Two design options are considered to store the data in the database:
- Put all the names in a single array and use binary search.
- Put the good customers in one array and the rest of them in a second array. Only if we do not find the customer on a binary search of the first array do we do a binary search of the second array.
Given the above two options, answer the following: i. Calculate the expected worst-case performance for each of the two structures above, given typical usage. Which of the two structures is the best option?
For this, I believe the worst case for binary search would be $\log_2(10000+1)$ which rounds up to 14. For the second scenario, it would be $\log_2(10000*.2+1)$ which is 11 if the customer is good and $\log_2(10000*.8+1)$ which is 13 if the customer is not good hence this would be the better scenario. Am I correct on this?
ii. Suppose that over time the usage of the database changes, and so a greater and greater fraction of lookups are for good customers. At what point does the answer to part i change?
If part i) was correct, then there is no scenario where x in $\log_2(10000*x+1)$ is greater than 15?
iii. Under typical usage again, suppose that instead of binary search we had used linear search. What is the expected worst-case performance of each of the two structures and which is the better option? Where is the cross-over this time?