Please show steps clearly

4. Consider the following function: Input : Array A of at least j elements. Integers i and j. Result : A permutation of the i through j elements of A such that A[i]A[i+1]A[i+2]A[j]. Function NearCenter returns an element p of S={A[i],A[i+1],A[i+2],,A[j]} whose rank is between n/8 and 7n/8, i.e., at least n/8 elements of S are less than or equal to p and at least 7n/8 elements of S are greater than or equal to p. Let n=ij+1 be the number of elements being sorted. Assume that function NearCenter takes cn time where n=ij+1 time. Partition is the function discussed in class and defined in the notes. What is the asymptotic worst-case running time of Sort3? Justify your solution