Discrete Math Resources

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???

edelossantosAsked:
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x
 
itsmeandnobodyelseConnect With a Mentor Commented:
Try yourself not using any URLs:

     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


0
All Courses

From novice to tech pro — start learning today.