# Quick sort analysis confusion

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?

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)$.
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.