analyzing algorithms ????

[it-lady]

Analysis of algorithms is a form of mathematics. Consider the following problem:
• We assume that a pair of squirrels has a pair of children every year.
• These children are too young to have children of their own until two years later.
• Squirrels never die.
(The last assumption sounds stupid, but makes the problem simpler. After we have analyzed the simpler version, we could go back and add an assumption e.g. that squirrels die in ten years, but it wouldn't change the overall behavior of the problem very much. However students who consider this case as well, will earn extra marks!)
1. Express the number of pairs of squirrels as a function P(n) of time (n is time measured as a number of years since the start of the experiment).
2. Develop an algorithm to compute P (n).
3. Use you program to calculate P(25) and P(250). Report and comment both results and execution times.
4. What is the time complexity of your algorithm, in Big-O notation? Explain why.

How can I solve this problem?

[frogboy77]

if u want i could just post you the code
save you the work

[it-lady]

ok if you would please?

[frogboy77]

shameless

[it-lady]

If you want to help me >> help please without embarrass me >>

Thank brother

[frogboy77]

if your "question"(i.e give me solution) does not embarrass you nothing i say will.
have you made any effort?

[mrnutty]

$100 dollars per homework, plus extra depending on the assignment. Or else you need to do this on your own, with some of us giving you hints.

[it-lady]

1-  P(1) = 1          // first pair of squirrels
    P(2) = 1         // still one pair because they have their own children after two years.
    P(3) = 2        //  they have a pair of children after two years.
    P(4) = 3       //  they have another pair (every year have a pair of children).
    P(5) = 5      // they have another pair and also first pair grandchildren.
    P(6) = 8     // they have another pair, first and second pair of grandchildren.
     .
     .
     .

P(n) = P(n-1) + P(n-2) 

2- 

#include <iostream>
using namespace std;

int main()
{

  int n, P, i,a , b;
  cout<<"Please enter the number of years ";
  cin>> n;
  cout<<endl<<"The number of pairs of squirrels are ";
  if ((n==1) || (n==2) )
  {
      P = 1;
  cout << P <<endl;
  }
  else 
{
    a = 1; 
    b = 1; 
    for (i=2; i< n; i++) 
        { 
              P = a + b;
              a = b;
      b = P;
           }
     cout<< b<<endl;
  }
  cout<<endl;
  return 0;
}
3-P(25) = 75025
   P(250) = -167647721, it does not work with huge numbers of years. 


4- The time complexity of this algorithm is 2ⁿ because each year depends on two previous years, like the following examples:

                    P(6)




                                    P(5)                             P(4)



                          P(4)            P(3)                P(3)               P(2)



        P(3)               P(2)  P(2)        P(1)   P(2)        P(1)  



P(2)        P(1)