What is worst case complexity of quick sort?

Answer 1

Selection sort has no end conditions built in, so it will always compare every element with every other element.

This gives it a best-, worst-, and average-case complexity of O(n2).

Answer 2

The time-complexity of merge sort is O(n log n).

At each level of recursion, the merge process is performed on the entire array. (Deeper levels work on shorter segments of the array, but these are called more times.) So each level of recursion is O(n). There are O(log n) levels of recursion, since the array is approximately halved each time.

The best-case time-complexity is also O(n log n), so mergesort takes just as long no matter what the existing state of the array.

Answer 3

The average and best-case complexity of QuickSort is O(n log n).

The worst-case is Quadratic (O(n2)).

The worst-case occurs when the chosen pivots are either the largest or smallest in the subarray. In this case, all the other values in the subarray will end up in one partition, with the others empty. The algorithm will then degenerate into something like InsertionSort (and a bad recursive implementation too!)

When the first item in the subarray is used for the partition, this has the ironic effect that an already sorted array is the worst-case. This problem can be avoided by randomly scrambling the array before sorting it (using Knuth's shuffling algorithm, perhaps). Another strategy is to switch to heap-sort when a certain recursion depth is reached.

Answer 4

The time complexity of q-sort algorithm for all cases:

average-O(n log(n))

worst- O(n2)

Answer 5

MergeSort has the same time-complexity in all cases, O(n log n). In fact, it has exactly the same absolute time, no matter what the state of the array.

Answer 6

T(n) = Θ(n2)

Answer 7

O(n2)

Answer 8

o(n)