Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > The worst case running times of Insertion sor... Start Learning for Free
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
- a)Θ(n log n), Θ(n log n) and Θ(n2)
- b)Θ(n2), Θ(n2) and Θ(n Log n)
- c)Θ(n2), Θ(n log n) and Θ(n log n)
- d)Θ(n2), Θ(n log n) and Θ(n2
Correct answer is option 'D'. Can you explain this answer?
Verified Answer
The worst case running times of Insertion sort, Merge sort and Quick s...
- Insertion Sort takes Θ(n2) in worst case as we need to run two loops. The outer loop is needed to one by one pick an element to be inserted at right position. Inner loop is used for two things, to find position of the element to be inserted and moving all sorted greater elements one position ahead. Therefore the worst case recursive formula is T(n) = T(n-1) + Θ(n).
- Merge Sort takes Θ(n Log n) time in all cases. We always divide array in two halves, sort the two halves and merge them. The recursive formula is T(n) = 2T(n/2) + Θ(n).
- QuickSort takes Θ(n2) in worst case. In QuickSort, we take an element as pivot and partition the array around it. In worst case, the picked element is always a corner element and recursive formula becomes T(n) = T(n-1) + Θ(n). An example scenario when worst case happens is, arrays is sorted and our code always picks a corner element as pivot.
Most Upvoted Answer
The worst case running times of Insertion sort, Merge sort and Quick s...
Insertion Sort:
Insertion sort is a simple sorting algorithm that works by repeatedly inserting an element from the unsorted part of the array into its correct position in the sorted part. The worst-case time complexity of insertion sort is O(n^2). This occurs when the input array is in reverse order, and for each element, it needs to be moved to the beginning of the sorted part of the array.
Merge Sort:
Merge sort is a divide and conquer algorithm that divides the input array into two halves, sorts them recursively, and then merges the sorted halves to obtain the final sorted array. The worst-case time complexity of merge sort is O(n log n). This is because the array is divided into halves recursively until the subarrays have only one element, and then the merging process takes place, which takes O(n) time.
Quick Sort:
Quick sort is also a divide and conquer algorithm that selects a pivot element from the array and partitions the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. The worst-case time complexity of quick sort is O(n^2). This occurs when the pivot is consistently chosen as the smallest or largest element in the array, resulting in unbalanced partitions. However, on average, quick sort has a time complexity of O(n log n), which makes it more efficient compared to insertion sort and merge sort.
Comparison of Worst Case Running Times:
Based on the above explanations, we can conclude that the worst-case running times of insertion sort, merge sort, and quick sort are as follows:
- Insertion Sort: O(n^2)
- Merge Sort: O(n log n)
- Quick Sort: O(n^2)
Therefore, the correct answer is option D: (n^2), (n log n), and (n^2).
Insertion sort is a simple sorting algorithm that works by repeatedly inserting an element from the unsorted part of the array into its correct position in the sorted part. The worst-case time complexity of insertion sort is O(n^2). This occurs when the input array is in reverse order, and for each element, it needs to be moved to the beginning of the sorted part of the array.
Merge Sort:
Merge sort is a divide and conquer algorithm that divides the input array into two halves, sorts them recursively, and then merges the sorted halves to obtain the final sorted array. The worst-case time complexity of merge sort is O(n log n). This is because the array is divided into halves recursively until the subarrays have only one element, and then the merging process takes place, which takes O(n) time.
Quick Sort:
Quick sort is also a divide and conquer algorithm that selects a pivot element from the array and partitions the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. The worst-case time complexity of quick sort is O(n^2). This occurs when the pivot is consistently chosen as the smallest or largest element in the array, resulting in unbalanced partitions. However, on average, quick sort has a time complexity of O(n log n), which makes it more efficient compared to insertion sort and merge sort.
Comparison of Worst Case Running Times:
Based on the above explanations, we can conclude that the worst-case running times of insertion sort, merge sort, and quick sort are as follows:
- Insertion Sort: O(n^2)
- Merge Sort: O(n log n)
- Quick Sort: O(n^2)
Therefore, the correct answer is option D: (n^2), (n log n), and (n^2).
 | Explore Courses for Computer Science Engineering (CSE) exam |  |
Top Courses for Computer Science Engineering (CSE)View all
Top Courses for Computer Science Engineering (CSE)
Question Description
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:a)Θ(n log n), Θ(n log n) and Θ(n2)b)Θ(n2), Θ(n2) and Θ(n Log n)c)Θ(n2), Θ(n log n) and Θ(n log n)d)Θ(n2), Θ(n log n) and Θ(n2Correct answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2026 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:a)Θ(n log n), Θ(n log n) and Θ(n2)b)Θ(n2), Θ(n2) and Θ(n Log n)c)Θ(n2), Θ(n log n) and Θ(n log n)d)Θ(n2), Θ(n log n) and Θ(n2Correct answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2026 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:a)Θ(n log n), Θ(n log n) and Θ(n2)b)Θ(n2), Θ(n2) and Θ(n Log n)c)Θ(n2), Θ(n log n) and Θ(n log n)d)Θ(n2), Θ(n log n) and Θ(n2Correct answer is option 'D'. Can you explain this answer?.
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:a)Θ(n log n), Θ(n log n) and Θ(n2)b)Θ(n2), Θ(n2) and Θ(n Log n)c)Θ(n2), Θ(n log n) and Θ(n log n)d)Θ(n2), Θ(n log n) and Θ(n2Correct answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2026 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:a)Θ(n log n), Θ(n log n) and Θ(n2)b)Θ(n2), Θ(n2) and Θ(n Log n)c)Θ(n2), Θ(n log n) and Θ(n log n)d)Θ(n2), Θ(n log n) and Θ(n2Correct answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2026 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:a)Θ(n log n), Θ(n log n) and Θ(n2)b)Θ(n2), Θ(n2) and Θ(n Log n)c)Θ(n2), Θ(n log n) and Θ(n log n)d)Θ(n2), Θ(n log n) and Θ(n2Correct answer is option 'D'. Can you explain this answer?.
Solutions for The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:a)Θ(n log n), Θ(n log n) and Θ(n2)b)Θ(n2), Θ(n2) and Θ(n Log n)c)Θ(n2), Θ(n log n) and Θ(n log n)d)Θ(n2), Θ(n log n) and Θ(n2Correct answer is option 'D'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE). Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:a)Θ(n log n), Θ(n log n) and Θ(n2)b)Θ(n2), Θ(n2) and Θ(n Log n)c)Θ(n2), Θ(n log n) and Θ(n log n)d)Θ(n2), Θ(n log n) and Θ(n2Correct answer is option 'D'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:a)Θ(n log n), Θ(n log n) and Θ(n2)b)Θ(n2), Θ(n2) and Θ(n Log n)c)Θ(n2), Θ(n log n) and Θ(n log n)d)Θ(n2), Θ(n log n) and Θ(n2Correct answer is option 'D'. Can you explain this answer?, a detailed solution for The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:a)Θ(n log n), Θ(n log n) and Θ(n2)b)Θ(n2), Θ(n2) and Θ(n Log n)c)Θ(n2), Θ(n log n) and Θ(n log n)d)Θ(n2), Θ(n log n) and Θ(n2Correct answer is option 'D'. Can you explain this answer? has been provided alongside types of The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:a)Θ(n log n), Θ(n log n) and Θ(n2)b)Θ(n2), Θ(n2) and Θ(n Log n)c)Θ(n2), Θ(n log n) and Θ(n log n)d)Θ(n2), Θ(n log n) and Θ(n2Correct answer is option 'D'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:a)Θ(n log n), Θ(n log n) and Θ(n2)b)Θ(n2), Θ(n2) and Θ(n Log n)c)Θ(n2), Θ(n log n) and Θ(n log n)d)Θ(n2), Θ(n log n) and Θ(n2Correct answer is option 'D'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
| Explore Courses for Computer Science Engineering (CSE) exam | |
Top Courses for Computer Science Engineering (CSE)
Explore Courses
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
