f(n) for n = 5

- f(5) = f((6)/2) + f((4)/2) = f(3) * f(2); // as n == 5 is odd

- f(3) = f((4)/2) + f((2)/2) = f(2) + f(1); // as n == 3 is odd

- f(2) = 2 + f((2)/2) = 2 + f(1); // as n == 2 is even

- f(1) = 1; // as n <= 1

That is the "recursion tree"

Then, write function f

int f(int n)

{

bool even = (n%2)==0; // no rest modulo 2

bool odd = !even;

if (n <= 1)

return n;

else if (even)

return ...

else /* if (odd) */

return ...

}

>>>> What is meant by determine the approximate space

Means, what is the maximal recursion depth (as a function of n) multiplied with the stack space needed for one call to f(int) (note, you don't need local bool variables 'even' and 'odd' as you could check the modulo condition in "else if" condition directly).

>>>> What is meant by time requirements for algorithms

"O n^2" means quadratic, "O log2 n" means logarithmic and "O n" means linear time requirements.

Look at the "tree" above and count number of calls of f(..) . Try n=2, n=3, n=4, n=6 and n=7 also ... If you would get

1: 1 call

2: 3 calls

3: 8 calls

4: 15 calls

5: 24 calls

6: 35 calls

7: 48 calls

it would be quadratic.

Regards, Alex