473,320 Members | 1,854 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Recursion - how long will be computing?

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
1 1207
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

226
by: Stephen C. Waterbury | last post by:
This seems like it ought to work, according to the description of reduce(), but it doesn't. Is this a bug, or am I missing something? Python 2.3.2 (#1, Oct 20 2003, 01:04:35) on linux2 Type...
43
by: Lorenzo Villari | last post by:
I've tried to transform this into a not recursive version but without luck... #include <stdio.h> void countdown(int p) { int x;
5
by: herrcho | last post by:
int main() { printf("Input a line: "); wrt_it(); printf("\n\n"); return 0; } void wrt_it() {
75
by: Sathyaish | last post by:
Can every problem that has an iterative solution also be expressed in terms of a recursive solution? I tried one example, and am in the process of trying out more examples, increasing their...
24
by: proctor | last post by:
hello, i have a small function which mimics binary counting. it runs fine as long as the input is not too long, but if i give it input longer than 8 characters it gives RuntimeError: maximum...
20
by: athar.mirchi | last post by:
..plz define it.
10
by: slix | last post by:
Recursion is awesome for writing some functions, like searching trees etc but wow how can it be THAT much slower for computing fibonacci- numbers? is the recursive definition counting fib 1 to...
0
by: Jean-Paul Calderone | last post by:
On Sun, 29 Jun 2008 10:03:46 -0400, Dan Upton <upton@virginia.eduwrote: CPython doesn't do tail call elimination. And indeed, function calls in Python have a much higher fixed overhead than...
35
by: Muzammil | last post by:
int harmonic(int n) { if (n=1) { return 1; } else { return harmonic(n-1)+1/n; } } can any help me ??
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.