Consider the following recursive function:

unsigned int foo(unsigned int n)

{

int i, tralalala_pointless_for_loop = 0;

if (n < 2) return 5;

for (i = 0; i < n; i++)

tralalala_pointless_for_loop++;

return foo(n-2);

}

Which of the following recurrence relations most accurately represents the runtime of this function?

a) Initial Condition: T(0) = T(1) = c0

Recurrence: T(n) = 5 + n for n 2

b) Initial Condition: T(0) = T(1) = c0

Recurrence: T(n) = 5 + T(n) for n 2

c) Initial Condition: T(0) = T(1) = 5

Recurrence: T(n) = 5 + n for n 2

d) Initial Condition: T(0) = T(1) = c0

Recurrence: T(n) = c1 + n for n 2

e) Initial Condition: T(0) = T(1) = c0

Recurrence: T(n) = c1 + T(n) for n 2

f) Initial Condition: T(0) = T(1) = c0

Recurrence: T(n) = c1 + T(n-1) for n 2

g) Initial Condition: T(0) = T(1) = c0

Recurrence: T(n) = c1 + T(n-2) for n 2

h) Initial Condition: T(0) = T(1) = c0

Recurrence: T(n) = c1 + n + T(n) for n 2

i) Initial Condition: T(0) = T(1) = c0

Recurrence: T(n) = c1 + n + T(n-1) for n 2

j) Initial Condition: T(0) = T(1) = c0

Recurrence: T(n) = c1 + n + T(n-2) for n 2

k) Initial Condition: T(0) = T(1) = c0

Recurrence: T(n) = c1 + n + 2T(n-1) for n 2