when qsort is activated first time key and = and = is incremented till it becomes because at position the value is greater than keyj is not decrementedbecause at position the value that we have is less than the key since <jwe interchange the rd element and th element then is incremented till it becomes and is decremented till it becomes since jwe interchange the key element that is the element at position with the element at position and call qsort recursively with the left sub-list made of elements from position to and right sub-list made of elements from position to as shown below notes indices right sub-list left sub-list by continuing in this fashionwe finally get the sorted list the average case time complexity of the quick sort algorithm can be decided as followswe assume that every time the list gets splitted into two approximately equal sized sub-lists if the size of given list is nthen it gets splitted into two sub lists of size approximately / each of these sub -lists further gets splitted into two sub-lists of size / and this is continued till the size becomes when the quick sort works with list of size it places the key element (which we take the first element of the list under considerationat its proper position in the list this requires no more than iterations after placing the key element at its proper position in the list of size nquick sort activates itself two times to work with left and right sub-listseach assumed to be of size / therefore if (nis time required to sort list of size since the time required to sort the list of size is equal to the sum of the time required to place the key element at its proper position in the list of size and the time required to sort the left and right sub-lists each assumed to be of size / (ncomes out to bet(nc* * ( / where is constant and ( / is the time required to sort the list of size / similarly the time required to sort the list of size / is equal to the sum of the time required to place the key element at its proper positions in the list of size and the time required to sort the left and right sub-lists each assumed to be of size / ( / comes out to bet( / * / * ( / where ( / is the time required to sort the list of size / ( / * / * ( / )and so on and finally we get ( (nc* ( * ( / ( / ) (nc* * ( / ) * * ( / * * *( / ( / ) ( * * * ( / * * ( / ( (log )* * nt( / )(log )* * nt( *(log * (nnlog(ntherefore we conclude that the average time complexity of the quick sort algorithm is (nlog dbut the worst case time complexity is of the ( the reason for this is in the worst case one of the two sub-lists will always be emptyand the other will be of the size ( - where is the size of the original list therefore in the worst case lovely professional university