Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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)$.
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.
