Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Discrete Math Resources

Posted on 2004-10-25
1
Medium Priority
?
208 Views
Last Modified: 2010-04-01
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???

0
Comment
Question by:edelossantos
[X]
Welcome to Experts Exchange

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
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 2000 total points
ID: 12402322
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

Featured Post

Tech or Treat!

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.

Question has a verified solution.

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

Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
Suggested Courses

604 members asked questions and received personalized solutions in the past 7 days.

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

Join & Ask a Question