#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    1
    Rep Power
    0

    Order of growth for two C functions


    Hi all,

    I'm new to computer science and I'm not sure about determining orders of growth, in terms of n, when recursion is involved. Consider these two C functions:

    Code:
    int p1(int x, int n) 
    {
        if (n==0){
            return 1;
         }
         return x*p1(x, n-1);
    }
    For this, I believe the order of growth to be n+1 because I think it has to iterate n times.

    For this function, I have even less of an idea:

    Code:
    int p2(int x, int n){
    
      if (n==0) {
        return 1;
     }
     if (n/2 * 2 ==n) {
        int r = p2(x, n/2);
        return r*r;
      }
      return  x*p2(x, n-1);
    }
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2012
    Posts
    103
    Rep Power
    3
    To determine the order of growth of a recursive function you need to use Recurrence Relations. If you have a divide and conquer algorithm, then you can apply the Master Theorem. There are a lot of YouTube videos that can explain what they are and how they work.

IMN logo majestic logo threadwatch logo seochat tools logo