Submit an article about your scariest tech experience—and the solution—and you’ll be automatically entered to win one of 4 fantastic tech gadgets.

Solved

Posted on 2004-10-25

I am looking for url and examples that will help me calculate the following:-> Formulas

f(n) = n if n <= 1;

f(n) = n + f(1/2 * n) if n is even, n > 1;

f(1/2 (n+1) )+ f(1/2 (n-1)) if n is odd, n > 1;

Draw the recursion tree and calculate the value of f(n) for n=5.

What is meant by determine the approximate space and time requirements for algorithms. -> How???

f(n) = n if n <= 1;

f(n) = n + f(1/2 * n) if n is even, n > 1;

f(1/2 (n+1) )+ f(1/2 (n-1)) if n is odd, n > 1;

Draw the recursion tree and calculate the value of f(n) for n=5.

What is meant by determine the approximate space and time requirements for algorithms. -> How???

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

- Help others & share knowledge
- Earn cash & points
- Learn & ask questions

1 Comment

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

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Course of the Month9 days, 3 hours left to enroll

Join the community of 500,000 technology professionals and ask your questions.