We want to sort an array A[1..n] using quicksort, where n is a power of 2. Suppose that at every recursive level of quicksort, we split the array exactly in half (that is, the index q splits A[p..r] into two subarrays A[p..q] and A[q + 1..r] with same number of elements (rp+ 1)/2). What is the running time of quicksort in this case? Please express this running time in O-notation, using the best asymptotic bound you can find. Justify your answer. (Hint: What is the height of the recursive calls tree in this case?)

If n is not a power of 2, does the best asymptotic bound on the running time for quicksort with this half-and-half split change?