Regarding Reduction of time compexity of any program

[cse.avinash]

Hello Sir,
I have problem regarding time complexity of any problem, whatever program I make, the time complexity exceeds.Is there any way to reduce the time complexity of the program.

If I use two nested for loops, order goes to O(n^2),is there any way to convert this order in O(n) or less than O(n^2).
please help me out. :(

[rubberman]

Show us what you are doing now.

[cse.avinash]

The fibonacci sequence is defined by the following relation:

F(0) = 0

F(1) = 1

F(N) = F(N - 1) + F(N - 2), N >= 2

there are t number of test cases.
Given two non-negative integers N and M, I have to calculate the sum (F(N) + F(N + 1) + ... + F(M)) mod 1000000007.

code with recursion:--

#include<stdio.h>
int fab(int);
int main()
{
    unsigned long m,n,t,j;
    int i,store,result;
    scanf("%lu",&t);
    for(j=0;j<t;j++)
    {
    store=0;
    scanf("%lu%lu",&n,&m);
    for(i=n;i<=m;i++)
    {
               store=store+fab(i);
    }
    result=store%1000000007;
    printf("%d\n",result);
    }
       return(0);
}
int fab(int num)
{
    if(num==0)
             return 0;
    else if(num==1)
         return 1;
    else 
         return (fab(num-1)+fab(num-2));
}

code without recursion:--

#include<stdio.h>
int fab(int);
int main()
{
    unsigned long m,n,t,j;
    int i,store,result;
  scanf("%lu",&t);
    for(j=0;j<t;j++)
    {
    store=0;
    scanf("%lu%lu",&n,&m);
    for(i=n;i<=m;i++)
    {
           store=store+fab(i);
    }
    result=store%1000000007;
    printf("%d\n",result);
    }
    return(0);

}
int fab(int num)
{
unsigned int i=0,j=1,sum=0,loop=1;
while(loop<=num)
{
i=j;
j=sum;
sum=i+j;
loop++;
}
return (sum);
}

[cse.avinash]

and the time complexity of the question is 5 secs.

[rubberman]

Given its doubly recursive nature, the only way to speed up a Fibonacci computation is to eliminate as much as possible the recursive nature of the algorithm. I have done that by creating an array of 47 or 93 values (largest numbers you can compute using 32-bit or 64-bit unsigned long integers), populating the first few elements with known values statically, and then computing the rest in an iterative (loop) rather than recursive manner. Similar methods can be used for other recursive algorithms in many cases.

FWIW, computing fib(93), which is 12200160415121876738, takes 0.002 seconds or less on my 3GHz Xeon processor system.

[cse.avinash]

sorry sir Question was incomplete, I am repeating my question once again.
The fibonacci sequence is defined by the following relation:

F(0) = 0

F(1) = 1

F(N) = F(N - 1) + F(N - 2), N >= 2

there are t number of test cases.
Given two non-negative integers N and M, I have to calculate the sum (F(N) + F(N + 1) + ... + F(M)) mod 1000000007.
T <= 1000
0 <= N <= M <= 10^9

time complexity 5 secs.

Creating an array means, I ve to define the array in program.
I cant understand it clearly, please Sir explain it with an example sir.

[rubberman]

I did this for c++ - testfib.cpp:

#include <stdlib.h>
#include <iostream>

using namespace std;

unsigned long long fib2(unsigned long long n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (n == 2) return 1;
    return (fib2(n-1) + fib2(n-2));
}

unsigned long long fib( unsigned long long n )
{
   unsigned long long array[n];

   if (n <= 10) return fib2(n);

   for (unsigned long long i = 0; i < 10; i++)
   {
      array[i] = fib2(i);
   }
   for (unsigned long long i = 10; i < n; i++)
   {
      array[i] = array[i-1] + array[i-2];
   }
   return array[n-1] + array[n-2];
}

int main( int argc, const char* argv[] )
{
    for (int i = 1; i < argc; i++)
    {
       cout << "fib(" << argv[i] << ") = " << dec << fib(strtoul(argv[i], 0, 10)) << endl;
    }
    return 0;
}

It would be easy enough to convert to C.