You are a programmer for the Committee to Abolish CS 32, which wants to conduct

Question

You are a programmer for the Committee to Abolish CS 32, which wants to conduct a voter registration drive in West Los Angeles and the Valley. You have a collection of registered voters in those areas, and you have obtained a collection of licensed drivers from there. You want to find all drivers who are not already registered to vote. Both the driver and voter collections are randomly ordered. Here are two algorithms you are considering: for each licensed driver, { found = false for each voter, if the driver under consideration == the current voter, found = true break } if not found, print the drivers name } sort the collection of voters by name, using a good algorithm sort the collection of drivers by name, using a good algorithm start with the first voter and the first driver while not done with the voter collection and not done with the driver collection, { if the current driver's name is alphabetically the voter go on to the next voter } print the remaining names, if any, in the driver collection suppose the driver collection and the voter each contain about N names, where N is large. Of the following choices, what is the average case time complexity of the two algorithms? The choices are O(1), O(log N), O(N), O(N log N), O(N^2), O(N^2 log N), O(N^3) Using a particular computer, you run an algorithm with time complexity O(N^2) and find that it takes a little under 2 1/2 hours to run using the West LA and Valley data. Suppose you wish LA and the valley. (California has about 20 million drivers) About how long would that algorithm take on the California data, using the same computer?

Explanation / Answer

Solution:

a)

In the problem statement it is mentioned that total of N drivers and N number of voters are there.

The Algorithm 1 has used a for loop which runs from 1 to number of licensed drivers which means that first algorithm will run n number of times, so big-O complexity will be O(N).

While the Algorithm2 has uses a good algorithm to sort the array, and we already know that for sorting best of the algorithms take N log N time. and the while loop is running for N number of times in for driver's collection to be compared with the voter's collection, this means O(n^2) time will be taken.

So the big-O will be O(n^2).

b)

So now 2.5 Hrs is taken to run the data of West LA and Valley data, but Califorrnia data is 10 times larger than these, so calculate time to process California data:

150 minutes taken for West LA and Valley data, 12.2475 minutes will be taken in a unit time

So for California 122.475 unit of time will be taken, and in total 15000 minutes will be taken.

that is 250 Hrs.

I hope this helps.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.