1- in one sentence what doSomething do?

2- Describe the worst case input and the worst case runtime. Give both a recurrence

relation and the big-Theta and justify your answers.

3- Describe the best case input and the best case runtime. Give both a recurrence

relation and the big-Theta and justify your answers.

Algorithm doSomething Input: an array A of size N Output: ??? foo(A, 0, N-1) procedure foo (Array A, int i, int j) if(i >= j) return if(i = A.Length 11 j >= A.Length)|| return int x = A[i] int p = i; int f = i + 1; for(int k = f; k