Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

C++ Programming

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

On 2007-06-06 17:37, Oberon wrote:

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 Wikstrm

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc