Complexity and Problem-Solving Strategy Question 12 (a) Say you have two sorting

Question

Complexity and Problem-Solving Strategy Question 12 (a) Say you have two sorting algorithms to compare and your goal is to select one of them to be used in a real-time application. Algorithm 1 has a worst plexityaf Q(),while algorithm 2 has a worst case time complexity OBoth have worst case space complexity of O(n). Which one would you say is a better sorting algorithm (1 or 2) for a reat-time application? 3 marks] , while al Briefly justify your answer (b) State in one sentence the esséice of the P versus NP problem. [2 marks]

Explanation / Answer

Dear Student,

Here only the worst case time complexity of the two algorithms is given.

Average case time complexity of both is required to reach any conclusion.

Worst case rarely occurs while execution. Average case complexity gives the idea of general execution behavior of the algorithms.

If best case and average case complexity of both algorithms is same then according to the worst case scenario given O(nlogn) is better than O(n2) ie. Algo. 2 is better.

Otherwise, nothing can be concluded without knowing about avg. case time complexity of both.

Thank You

For further queries, please feel free to ask. I would be glad to help :-)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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