This year, thousands of students took the SAT (Scholastic Aptitude Test) in New

Question

This year, thousands of students took the SAT (Scholastic Aptitude Test) in New Jersey in preparation to enter college. The total score on the SAT is out of 2400–scores are in multiples of 10. You are asked by the SAT office to write a program that will sort the students in descending values of their scores. If two students have the same score, it does not matter in which order they appear in the sorted result. Assume that the computer on which you will run your program has enough memory to store the names and scores of all the students, either in an array or in a linked list. Also, for this question, you can assume the number of students who took the SAT this year is exactly 65,536, which is 216.

1.) Assuming you were to use mergesort with linked lists, and counting only each score-to-score comparison as a unit time operation, how many such unit time operatons (not big O) would it take in the worst case to do the sort? Your answer must be simplified to the least possible number of terms.

Explanation / Answer

Least possible number of terms:

Let T(N) be the total number of comparisons needed to sort a list of size N

Thus T(N) = 2T(N/2) + N

T(N/2) = 2T(N/4) + N/2

Consider

T(1) = 0

Thus T(N) = 2k T(N/2k) + kN

Now let N/2k = 1

thus N = 2k

Thus k = log2 N

Thus T(N) = Nlog2N

Here N = 65536

Therefore, T(N) = 16*65536

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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