Describe best case and worst case scenarios for run time of following pseudo code:

Algorithm thisAlgo (int[] A : an array of N integers)

for(int i = N /2; i >= 0; i --):

foo (A , i )

end for

end thisAlgo

procedure foo(int[] A, int i)

int l = 2*i+1

int r = 2*i+2

if l >= A.length && r >= A.length:

return

if r >= A.length

if A[i] < A[l]:

swap A[i] and A[l]

return;

if A[r] > A[l] && A[r] > A[i]:

swap A[i] and A[r]

foo(A, r)

return;

if A[l] > A[i]:

swap A[i] and A[l]

foo(A, l)

end foo

Describe the best/worst case in terms of what the array would need to be to get the best or worst case. For example, could best case be for array in descending order?