1
$\begingroup$

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:

  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. 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?

$\endgroup$
  • $\begingroup$ Since you first search the list for good customers, the worst case second scenario time would actually be the sum of the two expressions you give. This will also change your later comments, i.e., crossover will exist. $\endgroup$ – kodlu Mar 30 '15 at 22:54
  • $\begingroup$ Would this make the worst case for the second scenario 11(.6)+13(.4)? Then how would I use this to find when this answer changes? (part ii) @kodlu $\endgroup$ – dms94 Mar 30 '15 at 23:07
1
$\begingroup$

You have two terms next to each other there that perhaps need clarification; "expected" and "worst-case". If I assume that "worst-case" means that the binary searches don't get lucky and "expected" means that we are working across a typical mix of customer orders, your answer to (i) is $0.6\cdot 11 + 0.4 \cdot(11+13) = 16.2 > 14$, so the separate lists are not worthwhile.

For (ii), in order to get the crossover point, define $k$ as the proportion of good customers and set $14 = k(11) + (1-k)(24) = 24-13k$, giving $k \approx 0.769$. So if we have 77% (or more) of orders from the good customers (which are still only 20% of the total customer base), separating the list for search purposes will be more efficient.

For (iii), I haven't done any calculation but I strongly expect that looking at the good customers first will always be preferable.


So adding for (iii), "worst-case" in the same sense as the binary search doesn't really work. Expected search length for the full list is $5000$ and for the split list is $0.6\cdot 1000 +0.4 \cdot (2000+4000) = 3000$, so the split list is easily better. Using the same approach as above to find the crossover, $5000 = k\cdot 1000 + (1-k) \cdot (2000+4000) = 6000-5000k$, that is, $k=0.2$ - the proportion of the good customers, as you would expect (if they're not buying more than anyone else, they're not really "good" any more).

$\endgroup$
  • $\begingroup$ The worst case for linear search would be 10,001 assuming the customer wasn't in the list which makes the crossover (calculated using the same k method) come out to -767 which doesn't seem logical. Did I miss something? $\endgroup$ – dms94 Mar 31 '15 at 0:47
  • $\begingroup$ @alivad Yeah, I don't think "worst case" is appropriate/useful to the linear case. Answer updated. $\endgroup$ – Joffan Mar 31 '15 at 1:53
  • $\begingroup$ I thought the worst case for linear search was just n+1, where did 5000 come from? $\endgroup$ – dms94 Mar 31 '15 at 14:47
  • $\begingroup$ Worst case is not useful, I used expected search length. $\endgroup$ – Joffan Mar 31 '15 at 15:05

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.