Time complexity program/recursive functions

This is a discussion on Time complexity program/recursive functions within the C++ Programming forums, part of the General Programming Boards category; It's a rather simple program, actually. It's a C++ program that will count the number of operations of two common ...

  1. #1
    Registered User
    Join Date
    Jul 2008
    Posts
    72

    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?

  2. #2
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    like factorial and fibonacci etc
    Here and here.
    Consider this post signed

  3. #3
    Registered User
    Join Date
    Jul 2008
    Posts
    72
    Quote Originally Posted by bernt View Post
    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.

  4. #4
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    Oh, sorry about that.
    Consider this post signed

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. NtSetSystemTime() failed
    By medp7060 in forum C++ Programming
    Replies: 11
    Last Post: 04-02-2010, 02:58 AM
  2. Journey time prog 1 minute wrong
    By mike_g in forum C Programming
    Replies: 4
    Last Post: 10-12-2006, 03:41 AM
  3. time Delays and Random functions
    By markphaser in forum C++ Programming
    Replies: 17
    Last Post: 02-20-2006, 06:10 PM
  4. The space time continueimnms mm... (rant)
    By Jeremy G in forum A Brief History of Cprogramming.com
    Replies: 32
    Last Post: 06-27-2004, 01:21 PM
  5. I apologize. Good bye.
    By doubleanti in forum A Brief History of Cprogramming.com
    Replies: 14
    Last Post: 05-03-2002, 06:51 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21