### Thread: Order of growth for two C functions

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. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2012
Posts
103
Rep Power
6
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.