Provide tight upper and lower bounds on the running time of the QUICKSORT algorithm below. Show your answer (the running time) in recurrence and solve the recurrence. Justify your answer to the two cases below.

(1) when all elements are in A[p...r] are distinct and sorted in ascending order?

(2) when all elements are in A[p...r] are distinct and sorted in descending order?

QuickSort(A, p, r)

if p < r

q = Partition(A, p, r)

QuickSort(A, p, q 1)

QuickSort(A, q + 1, r)

Partition(A, p, r)

x = A[r] # x is the pivot.

i = p 1

for j = p to r 1

if A[j] x

i = i + 1

exchange A[i] with A[j]

exchange A[i + 1] with A[r]

return i + 1