Consider the pseudocode below.

(a) What does it do? Note that I am looking for a high-level description of the task that it is performing, not a description of the details of the pseudocode.

(b) Describe the worst case input and the worst case runtime. Give both a recurrence relation and the big-Theta and justify your answers.

(c) Describe the best case input and the worst case runtime. Give both a recurrence relation and the big-Theta and justify your answers

Input: an array A of size N Output: ??? foo(A, 0, N-1) procedure foo (Array A, int i, int ;) if(i >= j) return if(i

= A.Length 1 j >= A.Length) return int x = A[i] int p = i; int f = i + 1; for(int k = f; k = j) return if(i
= A.Length 1 j >= A.Length) return int x = A[i] int p = i; int f = i + 1; for(int k = f; k