Consider the pseudo code:

a) What does this algorithm do?

A. It returns a list that contains the contents of L in reverse order.

B. It copies the contents of L over to a new list in the same order that they appear in L and returns that new list.

C. It sorts L in descending order.

D. It sorts L in ascending order.

E. None of the above.

b) Which of the following recurrence relations best describes the runtime of foo on a list of size N?

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

B. T(N) = T(N 1) + O(1); T(0) = O(1)

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

D. T(N) = T(N 1) + O(N); T(0) = O(1) E. T(N) = 2T(N 1) + O(1); T(0) = O(1)

c) What is the worst-case runtime of the algorithm in terms of N?

A. O(1)

B. O(logN)

C. O(N)

D. O(NlogN)

E. None of the above.

Algorithm foo (L := a linked list of size N) if L is empty: return 2 x := the first element in L remove x from the L M = foo(L) append x to the end of M return M