I was given the following algorithm:PARTITION(A,p,r)x <- A[p]i <- pj <- rrepeat    while A[i]<x        do i<-i+1    while A[j]>x        do j<-j-1    if i <= j        then exchange A[i] <-> A[j]until i>jreturn i,jquicksort(A, p, r):    if p<r    then i,j <- PARTITION(A,p,r)    QUICKSORT(A, p, j)    QUICKSORT(A, i, r)And I was asked to find the quicksort run time at best, worst and average cases.I did okay for the best and worst, however I'm having difficulties with the average case. I'm pretty sure it's still $O(nlgn)$, but I can't prove it formally, mainly showing how many time the partition method is called at most.Could anyone help me with that?Thanks! 
Partition algorithm average-case complexity analysis
algorithm analysis;runtime analysis;quicksort;average case