CODEWITHSUNDEEP
algorithmrecursiontime-complexity
manali sikdar
manali sikdar

Reputation: 13

Recurrence relation for a hypothetical recursive function

What is the method to find time complexity for recursive programs? Let's take this code as an example.

int hypo(int a, int n) 
{ 
     if(n == 1) 
         return 0; 
     else 
         return a + hypo(a,n-1) * hypo(a,n-1); 
}

Upvotes: 0

Views: 221

Answers (2)

anatolyg
anatolyg

Reputation: 28241

The first thing you have to do is write the equation that specifies the running time (this is often straightforward, and doesn't involve any solving). In your example, you denote by f(a, n) the running time of the function for parameters a and n, and then:

  • f(a, n) doesn't depend on a, so let's write it f(n) instead
  • f(1) is a constant; let's denote it by k
  • If n > 1, then f(n) = c + 2 * f(n-1), where c is a constant (another one)

So now you need to find out which function satisfies the equations f(n) = c + 2 * f(n-1) and f(1) = k. There is no general method, but in your case it's easy to calculate f(2), f(3), ...:

f(2) = c + 2 * f(1) =      c +  2 * k
f(3) = c + 2 * f(2) =  3 * c +  4 * k
f(4) = c + 2 * f(3) =  7 * c +  8 * k
f(5) = c + 2 * f(4) = 15 * c + 16 * k

It seems pretty easy to find f(n) from here (you can prove the formula by induction, or just say "it's obvious").

Upvotes: 1

btilly
btilly

Reputation: 46399

Most simple problems of this form can be solved with the Master Theorem. See http://en.wikipedia.org/wiki/Master_theorem.

More complex methods exist for more complex problems. :-)

Upvotes: 1

Related Questions