Discussion
Which of the following sorting does not have worst case running time of O(n\(^{2}\)) ?
Answer: A
Merge sort (printed 'Merger sort') does not have an O(n\(^{2}\)) worst case.
Merge sort always splits the list into halves and merges them in linear time, so its running time is O(n log n) in every case, including the worst.
Quick sort is O(n log n) on average but O(n\(^{2}\)) in the worst case, when pivots split the list very unevenly, as with already sorted input and a first-element pivot. Insertion sort and bubble sort are O(n\(^{2}\)) in the worst case, on reverse-sorted input.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development