A company database has 10,000 customers sorted by last name, 20% of whom are known to be good customers. Under typical usage of this database, 60% of lookups are for the good customers. Two design options are considered to store the data in the database:

  1. Put all the names in a single array and use binary search.

  2. Put the good customers in one array and the rest of them in a second array. If we do not find the query name on a binary search of the first array, we do a binary search of the second array.

Given these 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?

My approach:

In the worst case for binary search, when the value is not in our array, the algorithm must continue iterating until the span has been made empty; this will have taken at most $log2(N)+1$ iterations. In our situation, it is $log2(10000)+1 = 13.28+1 = 14.28 = 15$? Not sure i'm on the right track. How does 20% of 10000 are good customers and 60% lookups are for good customers taking into account this problem?

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?

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?


Let $X \equiv$ the number of iterations needed in the worst case for the second scenario. Notice that: $$ X = \begin{cases} \lceil \log_2(0.2 \cdot 10000) \rceil + 1 = 12 &\text{if customer is good} \\ \lceil \log_2(0.8 \cdot 10000) \rceil + 1 = 14 &\text{otherwise} \\ \end{cases} $$ and: $$ P(X = x) = \begin{cases} 0.6 &\text{if }x = 12 \\ 0.4 &\text{otherwise} \\ \end{cases} $$ Hence, the average number of iterations is: $$ E(X) = \sum_x x \cdot P(X = x) = 12(0.6) + 14(0.4) = 12.8 $$ which is smaller than $15$, and so is more efficient than the second scenario.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.