complexity of quick sort in the average casethe running time of quick sort can be given as ( log nthe partitioning of the array which simply loops over the elements of the array once uses (ntime in the best caseevery time we partition the arraywe divide the list into two nearly equal pieces that isthe recursive call processes the sub-array of half the size at the mostonly log nested calls can be made before we reach sub-array of size it means the depth of the call tree is (log nand because at each levelthere can only be ( )the resultant time is given as ( log ntime practicallythe efficiency of quick sort depends on the element which is chosen as the pivot its worst-case efficiency is given as ( the worst case occurs when the array is already sorted (either in ascending or descending orderand the left-most element is chosen as the pivot howevermany implementations randomly choose the pivot element the randomized version of the quick sort algorithm always has an algorithmic complexity of ( log npros and cons of quick sort it is faster than other algorithms such as bubble sortselection sortand insertion sort quick sort can be used to sort arrays of small sizemedium sizeor large size on the flip sidequick sort is complex and massively recursive programming example write program to implement quick sort algorithm #include #include #define size int partition(int []int begint end)void quick_sort(int []int begint end)void main(int arr[size]inprintf("\ enter the number of elements in the array")scanf("% "& )printf("\ enter the elements of the array")for( = ; < ; ++scanf("% "&arr[ ])quick_sort(arr - )printf("\ the sorted array is\ ")for( = ; < ; ++printf(% \ "arr[ ])getch()int partition(int []int begint endint leftrighttemplocflagloc left begright endflag while(flag ! while(( [loc< [right]&(loc!=right)right--