notes (ncomes out to bet(nc* + ( - * *( - ( - * * ( - * * *( - ( - * * * ( - * * - * ( -nc+ therefore (nn hence the order is ( space complexity the average case space complexity is log nbecause the space complexity depends on the maximum number of activations that can exist we find that if we assume that every time the list gets splitted into approximately two lists of equal size then the maximum number of activations that will exist simultaneously will be log in the worst casethere exist activations because the depth of the recursion is hencethe worst case space complexity is (nalgorithms of quick sort the divide-and-conquer strategy is used in quicksort below the recursion step is described choose pivot value we take the value of the middle element as pivot valuebut it can be any valuewhich is in range of sorted valueseven if it doesn' present in the array partition rearrange elements in such waythat all elements which are lesser than the pivot go to the left part of the array and all elements greater than the pivotgo to the right part of the array values equal to the pivot can stay in any part of the array noticethat array may be divided in non-equal parts sort both parts apply quicksort algorithm recursively to the left and the right parts partition algorithm in detail there are two indices and and at the very beginning of the partition algorithm points to the first element in the array and points to the last one then algorithm moves forwarduntil an element with value greater or equal to the pivot is found index is moved backwarduntil an element with value lesser or equal to the pivot is found if < then they are swapped and steps to the next position ( ) steps to the previous one ( algorithm stopswhen becomes greater than after partitionall values before -th element are less or equal than the pivot and all values after -th element are greater or equal to the pivot lovely professional university