Question

Say you have a random, unordered list containing 4096 four-digit numbers. Describe the most efficient way to: sort the list and then search for 100 elements within the list, and analyze the expected run time for this specific list's sorting and searching.

Answer 1

Answer:

Answer explained below

Explanation:

It is given that numbers are four-digit so maximum value of a number in this list could be 9999.

So we need to sort a list of integers, where each integer lies between [0,9999].

For these given constraints we can use counting sort which will run in linear time i.e. O(n).

--------------------------------------------------------------------------------

Psuedo Code:

countSort(int numList[]) {

int count[10000];

count[i] = 0; for all i;

for(int num in numList){

count[num]+= 1;

}

return count;

}

--------------------------------------------------------------------------------

Searching in this count array will be just O(1).

E.g. Lets say we want to search if 3 was present in the original list.

Case 1: it was present in the original list:

Then the count[3] would have been incremented by our sorting algorithm. so in case element exists then count value of that element will be greater than 0.

Case 2: it was not present:

In this case count[3] will remain at 0. so in case element does not exist then count of that element will be 0.

So to search for an element, say x, we just need to check if count[x]>0.

So search is O(1).

Run times:

Sorting: O(n)

Search: O(1)