Thread: Time complexity program/recursive functions

It's a rather simple program, actually.

It's a C++ program that will count the number of operations of two common recursive functions.
This operation count will be basically estimate time complexity T(n). It has to find the g(n) to getO(g(n)).The program takes as input n, some positive integer and choosing between a recursive or non-recursive version. It needs to evaluate two recursive functions: factorial(n)=n! and fibonacci(n)=fibonacci(n-1)+fibonacci(n-… (starting at fibonacci(1)=0 and fibonacci(2)=1).
The program will be required to produce one line of output per function showing result, operation count (T(n)) and worst-case time complexity with O(g(n)) exhibiting c and some n0, according to the definition (n0 greater than 2). You must find the right c value so that the inequality always holds.

This is as far as I get:

Code:

// global
int numOps;

void SomeRecursiveRoutine(int n)
{
    if( n == 0)
        return;
    numOps++;
    SomeRecursiveRoutine(n-1);
}


void SomeNonRecursiveRoutine(int n)
{
    for(int i = 0; i < n; i++)
    {
        numOps++;
    }
}

int main(int argc, char* argv[])
{
    time_t start;
    time_t end;

    int n= atoi(argv[1]);

    numOps = 0;
    // fill in start
    SomeRecursiveRoutine(n);
    // fill in end.
    // subtract end - start for time.  Also display numOps.


    numOps = 0;
    // fill in start
    SomeNonRecursiveRoutine(n);
    // fill in end.
    // subtract end - start for time.  Also display numOps.


    return 0;
}

The inputwill come from a text file, which is gonna look like this:

factorial(3)=6
fibonacci(3)=1
factorial(6)=720
fibonacci(6)=5

The outputwill be put into another text file and look like this:

http://img836.imageshack.us/img836/3476/outputf.png


I already have the output code, input code and the code above. There's obviously some stuff missing... like factorial and fibonacci etc. I have no clue how to do the calculations. And I already read up on the math part. Does anybody know how to do this?

Originally Posted by bernt

Here and here.

I obviously did that, but it needs to evaluate the function, do the operation count (T(n)) and worst-case time complexity with O(g(n). I don't get it.