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

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