Time complexity of doubly recursive function

Question

So this is the code:

int test ( int n) 
{ 
   if (n ≤2) return 1; 
   else return test(n-2) * test(n-2); 
}

I'm not confident in how to reason about this recursive function. I tried mapping the N value to the recursion depth like so:

N = 2 -> 0 recursions
N = 4 -> 2
N = 8 -> 14

But to be honest I'm not sure this gets me anywhere (and just thinking about test(16) hurts my head.

you know that you can make the method much more efficient by changing return test(n-2) * test(n-2) into { int y=test(n-2); return y*y; }? A single trivial change can turn a O(2^n) function into an O(n) function. — Michael
– Michael, Commented Jan 17, 2016 at 13:22

templatetypedef · Accepted Answer · 2016-01-09 18:04:32Z

Let's start by writing out a recurrence relation for the total number of calls made:

T(0) = T(1) = T(2) 1, since there's one total call (the initial call).
T(n+2) = 2T(n) + 1, since there's one call for the initial call, plus two recursive calls to problems of size n.

Let's start by looking at the case where n is even. Then

T(0) = 1
T(2) = 1
T(4) = 2T(2) + 1 = 3
T(6) = 2T(4) + 1 = 7
T(8) = 2T(6) + 1 = 15
T(9) = 2T(8) + 1 = 31

Except for the 0 case, it looks like these values take on the pattern 1, 3, 7, 15, 31, etc. Notice that each of these is one less than a power of two: 1 = 2 - 1, 3 = 4 - 1, 7 = 8 - 1, etc. We can guess that what we're looking at has something to do with powers of two.

Going back to our sequence, we might make a guess that

T(2) = 1 = 2¹ - 1
T(4) = 3 = 2² - 1
T(6) = 7 = 2³ - 1
...
T(2n) = 2ⁿ - 1

So if n is even, we have T(n) = 2^n/2 - 1 = (√2)ⁿ - 1. You can formalize this using a proof by induction.

For the odd case, we basically get the same thing:

T(1) = 1
T(3) = 2T(1) + 1 = 3
T(5) = 2T(3) + 1 = 7
T(7) = 2T(5) + 1 = 15
T(9) = 2T(7) + 1 = 31
...
T(2n+1) = 2ⁿ - 1

So if n is even, then T(n) = 2^(n-1)/2 - 1. Again, you can prove this by induction to formalize things if you'd like.

Collectives™ on Stack Overflow

Time complexity of doubly recursive function

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related