+1 vote
61 views

Choose the correct alternatives (More than one may be correct).

The complexity of comparision based sorting algorithms is:

1. $\Theta (n \log n)$
2. $\Theta (n)$
3. $\Theta \left(n^2\right)$
4. $\Theta (n\sqrt n)$

Only A & C are possible in Comparision based sorting

Algorithm Time Complexity
Average Worst
Quicksort O(n log(n)) O(n^2)
Mergesort O(n log(n)) O(n log(n))
Heapsort O(n log(n)) O(n log(n))
Bubble Sort O(n^2) O(n^2)
Insertion Sort O(n^2) O(n^2)
Select Sort O(n^2) O(n^2)
edited
When question says "The complexity of comparision based sorting algorithms" we should consider all comparison based algorithms together and not separately. So, answer must be A and C is false.

@Arjun sir Isn't the question is asking what are the complexities possible in comparision based sorting

Just option A is Θ(nlogn) whereas for selection sort and bubble sort Θ(n2)

So we should consider both