algorithm order

[hooshdar3]

Hello
sorry.Can you help me determine the order of the alggorithm
T(n) = T(n-1) + (n-1)/n(n + 1)

?

Thanks in advance!

[iamlms]

Not very understand what is the problem.
In fact it can be written in C++ by a recursive function:

Given that T(0) = 0 ( other initial value also ok)


#include <iostream>
using namespace std;

double T(unsigned int n)
{
if(n==0)
return 0;
return T(n-1) + double(n-1)/double(n*(n+1));
}

int main()
{
double to=T(5);
cout<<to<<endl;
}

Output is: 0.616667

[ResidentBiscuit]

Order? Complexity? I think I've heard order get used like that before. In which case, it's linear complexity.

[hooshdar3]

Not very understand what is the problem.
In fact it can be written in C++ by a recursive function:

Given that T(0) = 0 ( other initial value also ok)


#include <iostream>
using namespace std;

double T(unsigned int n)
{
if(n==0)
return 0;
return T(n-1) + double(n-1)/double(n*(n+1));
}

int main()
{
double to=T(5);
cout<<to<<endl;
}

I changed the program a bit to fit the purpose of the question;With your permission:

#include <iostream>
using namespace std;
int i = 0;

double T(unsigned int n)
{
       ++i;
    if(n==0)
    return 0;

    return T(n-1) + double(n-1)/double(n*(n+1));
}

int main()
{
   double to=T(5);
   cout<< i <<endl;
   
   cin.get();
   return 0;  
}

[ne555]

I think that the question is the growth of T(n)
In which case it's logarithmic because it approximates to the harmonic series.

[hooshdar3]

I think that the question is the growth of T(n)
In which case it's logarithmic because it approximates to the harmonic series.

are you surre?Order of magnitude is different from the valu computed.It can compute any value.

Otherwise, why would it call itself n times?

Size of the problem is reduced by just 1 each time.

I just changed T(5) to T(1000) and it makes no difference.

[ne555]

You could solve the recurrence, and get the result in constant time. (that's what I did)
¿Does that make the algorithm constant?

They give you the time that it takes to compute the algorithm.
You are responding with the time that it takes to compute the time that it takes the algorithm.


By instance, the time of merge sort

T(n) = 2 T(n/2) + C n