Consider th following cases for quick sort to sort an array of n element $a[0...n-1]$

i) Choosing the pivot element randomly from the given array

ii) choosing median element as pivot.

Iii) Choosing middle element as pivot

For which of the above cases quick sort always gives $O(nlogn)$ time complexity?