Consider the pseudo code below

1a.

Which recurrence relation best describes the runtime of foo?

1. T(N) = T(N-1) + O(1);

T(1) = O(1)

2. T(N) = T(N/2) + O(1);

T(1) = O(1)

3. T(N) = 2T(N/2) + O(1);

T(1) = O(1)

4. T(N) = T(N/2) + O(N);

T(1) = O(1)

5. None of the above

1b.

What is the run time?

1. (N)
2. (NlogN)
3. (N^2)
4. (N^2logN)
5. None of the above

foo(b : int, N : int): if(N = 1) return b num foo(b, floor(N/2)) if(N mod 2 = 0) return num * num else return b * num num *