For the following questions, I understand that you cannot give exact answers. Bu

Question

For the following questions, I understand that you cannot give exact answers. But you should understand that it is possible to give an educated computation that displays some understanding of the running time of the algorithm under consideration. I want you to give me this educated computation. Saying "I cannot tell exactly" will earn you zero points. (a) Assume that you are running Bubble sort on your machine and it takes 1 second to sort 1000 items. How long will it take on the sae machine, under the same conditions, to sort 106 items of the same type, and why? (b) Assume that you are running Heap sort on your machine and it takes 1 second to sort 1000 items. How long wil it take on the same machine, under the same conditions, to sort 106 items of the same type, and why?

Explanation / Answer

Hello Student!

I am happy to help you!

Conisdering all the conditions are same. For both the algos

(a) Coming over to bubble sort, The worst-case time complexity of bubble sort is O(n2). Therefore, for sorting n elements it will take n2 operations.

If it takes 1 sec to sort 1000 elements.

then, How much time will it take to sort 1,000,000 numbers.

Cost per operation 1000 elements will have 1,000,000 operations as its worst case complexity is O(n2). Therefore, it performs 1,000,000 operations in 1 sec.

For, 1,000,000 the operations performed will be 1,000,000,000,000

Now, for 1,000,000 it takes 1

then, for 1,000,000,000,000 it will take 1 * (1,000,000,000,000)/(1,000,000)

That is - 106 seconds = 227.78 hrs = 11.57 days.

(b) Coming over to heap sort, The worst-case time complexity of heap sort is O(nlogn). Therefore, for sorting n elements it will take nlogn operations.

If it takes 1 sec to sort 1000 elements.

then, How much time will it take to sort 1,000,000 numbers.

Cost per operation 1000 elements will have 9,965 (10,000 approx) operations as its worst case complexity is O(nlogn). Therefore, it performs 10,000 operations in 1 sec. (log with base 2)

For, 1,000,000 the operations performed will be 19,931,567 (20,000,000 approx)

Now, for 10,000 it takes 1

then, for 20,000,000 it will take 1 * (20,000,000)/(10,000)

That is - 2,000 seconds = 0.57 hrs

Thank you. Feel free to ask anything. Please upvote the answer, if you like it. Thank you again.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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