Mathematical Operations

[XodoX]

I want to do the following:

You will create 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). You have to find the g(n) to get O(g(n)).
The program takes as input n, some positive integer and choosing between a recursive or non-recursive version. You will evaluate two recursive functions: factorial(n)=n! and fibonacci(n)=fibonacci(n-1)+fibonacci(n-2) (starting at fibonacci(1)=0 and fibonacci(2)=1).
Your 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.

I have no idea how I can do this. Is there anybody who knows? Sounds so difficult.

Few input examples....

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

[Akill10]

http://www.cplusplus.com/forum/articles/2231/
http://www.cplusplus.com/doc/tutorial/functions2///scroll near to the bottom

[XodoX]

Ugh,I read a lot of stuff, but I still have no idea how to do this. I can't even figure out what they actually want. Like, "You have to find the g(n) to get O(g(n))." No idea.

[VernonDozier]

Well, first you have to write the programs themselves. Then set up some counters for the number of operations and do some time calculations. After that, start plotting and find a math equation. Note that you might need something more precise than seconds.

// 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;
}

Run for several n values and find a formula. Do it for factorial and fibonacci.

[XodoX]

Thanks. What do you mean by find a math equation? Those are already defined.

[VernonDozier]

Thanks. What do you mean by find a math equation? Those are already defined.

You have the number of operations for each n, so you get a bunch of paired data points. So if it was something like:

(1,1)
(2,4)
(3,8)
(4,16)
(5,25)

That would be O(n^2)

If it was

(1,1)
(2,2)
(3,3)
(4,4)
(5,5)

that would be O(n)

Or it could be O(n^3) or O(n^4) or O(nlogn) or whatever. That's the whole point of the assignment.

You take the ordered pairs and find the relationship. Ditto with the time points.

[XodoX]

Ok, i've tried that now, but I still have no clue how this works. I mean the functions themselves aren't difficult, but I can't apply it. Like choosing between a recursive or non-recursive version, and evaluating the functions. I can't find a sample code for my case either, for this case.