Question
this is a search algorithms problem for discrete math and I was having trouble with calculating which of the two structures is the best option and I dont understand part three at all.
A company database has 10,000 customers sorted by last name, 30% 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. Only if we do not find the query name on a binary search of the first array do 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? 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? ii. 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?
Explanation / Answer
Is O(n), cuz you iterate along the data n times.
Something that is O(n^2) (N squared) would be an iteration inside an iteration.
Like:
var i=0;
var x=0;
var n=10;
for (i=1;i<n;i++){ for (x=1;x<n;x++){ console.log(i);
}
}
