0
$\begingroup$

Is randomized quick sort runtime is independent of the sequence of input? but depends on the numbers in the input?

Let say A1 = [1,2,3,4,5] , A2 = [5,2,3,4,1] A3 = [5,4,3,2,1] , Will the randomized Quick sort will have same runtime in terms of big O for A1, A2, A2

but for B1 = [1,2,3,4,5] B2 = [11,12,13,14,15] will have different runtime i.e. depends on the digits in the input?

$\endgroup$

2 Answers 2

1
$\begingroup$

Will the randomized Quick sort will have same runtime in terms of big O for A1, A2, A2

Statements like this do not make any sense. For any given input, any algorithm has running time O(1).

Note that Landau notation (here) inherently contains a "for size to infinity" clause. Therefore, it makes only sense for infinite input sets.

Then, yes, the result depends a lot on the input sequences you consider. If you average over all inputs, you get $\Theta(n \log n)$. If you average over all worst-case inputs, you get $\Theta(n^2)$.

$\endgroup$
0
$\begingroup$

The runtime of the randomized quick sort algorithm does depend on the sequence of the input (if you mean the order of the elements in the array).

Since this algorithm chooses a random element as the pivot, the running time for the arrays $A_1$, $A_2$, and $A_3$ may be same or different each time you run this algorithm. But in general, expected (average) running time of the randomized quick sort algorithm is $O(n\log n)$ and its worst-case running time is $O(n^2)$. The purpose of randomization (shuffling for example) is to make the worst-case unlikely.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.