The following algorithm STOOGE-SORT(A, 0, n-1) recursively sorts a list of n numbers in A[n] in increasing order.

STOOGE-SORT(A, i, j) //initially: i=0, j=n-1

if (i+1==j) &&(A[i] > A[j]) //two elements

exchange( A[i], A[j])

if i+1 j then //if the input is empty or has one element

return

k = floor[ (j - i + 1)/3 ] //round down to the one third position

STOOGE-SORT(A, i, j-k) //the first two-thirds of the input array

STOOGE-SORT(A, i+k, j) //the last two-thirds of the input array

STOOGE-SORT(A, i, j-k) //the first two-thirds of the input array again

Please represent the running time of STOOGE-SORT() as a recurrence equation T(n), where n is the size of the input array. Then submit your answer.