As part of an assignment, a student writes generic code to sort an array of diff

Question

As part of an assignment, a student writes generic code to sort an array of different objects. The student decided that she will split the array into several small sets, and sort those, merging them all back together. In initial tests on edoras using an array of 50 elements, the code takes 3 second to run. The professor tests the code that was turned in on edoras with a larger array, containing 400 elements, and on the same computer it took 192 seconds to run. a) How long will it take to run this code on an array with 5,000 elements? Explain your answer. b) What is the complexity of the algorithm that the student wrote? Explain your answer. c) If this was a O(log n) algorithm, how many seconds would it take to run 400 elements? Explain your answer.

Explanation / Answer

for 50 elements, running time = 3 sec

when the input size is 8 times (i.e 400), running time = 3 * 8*8 = 192

So, the running time is proportional to the square of the input size.

If the input size is 5000, running time will be 3 * (100*100) = 30000 sec

The time complexity of the algorithm is O(n2) where n is the input size.

if it was O(log n), time taken would be 3 * log2 8 = 9 sec

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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