To sort or not to sort: Outline a reasonable method of solving each of the follo

ID: 3545762 • Letter: T

Question

To sort or not to sort: Outline a reasonable method of solving each of the following problems. Give

the order of the worst-case complexity of your methods.

a. You are given a pile of thousands of telephone bills and thousands of checks sent in to pay the bills.

(Assume telephone numbers are on the checks.) Find out who didn't pay.

b. You are given an array in which each entry contains the title, author, call number, and publisher of all the

books in a school library and another array of 30 publishers. Find out how many of the books were

published by each of those 30 companies.

c. You are given an array containing checkout records of all the books checked out of the campus library

during the past year. Determine how many distinct people checked out at least one book.

Store telephone bills and checks in two saperate hash tables.

Hash table: It is an array.For example if a check of Rs.300 is give increment arraycheck[300] by 1 and similarly for bills.

Iterate the hash tables and check how many bills are not paid.

For example, if arraybill[i]-arraycheck[i]=x , then increment unpaid bills by x.

So,order of the worst-case complexity:==> O(n) where n is largest amount among all the telephone bills.

_____________________________________

b)
Maintain an answer array to store no.of books published by publishers in array2;

For all the 30 publishers check how many books are published by iterating over the firstarray and store it in answerarray.

We will get a double for loop but outer for loop is only 30 iterations.

So,order of the worst-case complexity=O(30*n)

=O(n) ;Here n is the no.of entries in the first array.

____________________________________

C) Let n be the total no. of checkout records,

Maintain an answer array to store no of distinct persons and inttiate this array to 0;

for all the entries in the given array

------>make answerarray[person]=1;

end loop;

count no.of ones in the answer array by iterating through that array and that gives you the answer.

So,order of the worst-case complexity=O(n); Here n=no.of entries in the array

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