By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,332 Members | 1,404 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,332 IT Pros & Developers. It's quick & easy.

Recursion - how long will be computing?

P: n/a
Hi.
I wrote algorithm

double G(int m , int n){
if(m<0 || m>n){
return 0;
}
if (m==0 && n==0){
return P_G;
}
else{
return (G(m,n-1)*P_GG + B(m,n-1)*P_BG );
}
}

double B(int m, int n){
if(m<0 || m>n){
return 0;
}
if (m==0 && n==0){
return P_B;
}
else{
return ( B(m,n-1)*P_BB*NE_B + G(m,n-1)*P_GB*NE_B +
B(m-1,n-1)*P_BB*E_B +G(m-1,n-1)*P_GB*E_B );
}
}

In main i compute P(m,n) = G(m,n)+ B(m,n)

For small n (n<20) it compute in few seconds but i would like to
compare results with the results from literature (n=100)

The total number of computations is :
16n^2 multiplications
6n^2 additions

After 1 hour it didnt compute (m=10 ,n=100) (Core duo (notebook)
1.6Ghz)

How long it will compute ? or the algorithm is wrong build (any
errors ?? ))

Thanks

Jun 6 '07 #1
Share this Question
Share on Google+
1 Reply


P: n/a
On 2007-06-06 17:37, Oberon wrote:
Hi.
I wrote algorithm

double G(int m , int n){
if(m<0 || m>n){
return 0;
}
if (m==0 && n==0){
return P_G;
}
else{
return (G(m,n-1)*P_GG + B(m,n-1)*P_BG );
}
}

double B(int m, int n){
if(m<0 || m>n){
return 0;
}
if (m==0 && n==0){
return P_B;
}
else{
return ( B(m,n-1)*P_BB*NE_B + G(m,n-1)*P_GB*NE_B +
B(m-1,n-1)*P_BB*E_B +G(m-1,n-1)*P_GB*E_B );
}
}

In main i compute P(m,n) = G(m,n)+ B(m,n)

For small n (n<20) it compute in few seconds but i would like to
compare results with the results from literature (n=100)

The total number of computations is :
16n^2 multiplications
6n^2 additions

After 1 hour it didnt compute (m=10 ,n=100) (Core duo (notebook)
1.6Ghz)

How long it will compute ? or the algorithm is wrong build (any
errors ?? ))
If the number of multiplications and additions is correct then you have
a quadratic running time, meaning that the time it takes to run the
program is proportional to the quadrate of n. Try running with smaller
numbers first (10, 20, 30, 40, ...) and see how long it takes and you
should be able to get a figure. If you have a better calculator it
should be able to figure out the function to calculate the time based on n.

Notice thought that since you have a recursive function it is possible
that you'll run out of stack-space before completing the computation. It
is sometimes (always?) possible to rewrite the code to use a normal loop
and store values of previous iterations in an array, which will be more
space efficient and often run much faster.

--
Erik Wikström
Jun 6 '07 #2

This discussion thread is closed

Replies have been disabled for this discussion.