1

How to find a complexity of the following algorithm:

int f(int n)
{
  if(n<=1) { return 1; }
  return f(n-1) + f(n-1);
}

Is it correct recursion equation T(n) = 2*T(N-1) + c? How to solve it?

  • [Determining complexity for recursive functions (Big O notation)](http://stackoverflow.com/a/13467808/1734730) looks related. – Nathan Cooper May 25 '16 at 14:52
  • 1
    Wikipedia page on this topic https://en.wikipedia.org/wiki/Master_theorem – Aaron May 25 '16 at 14:55
  • Actually， you can speed up the function by memo f(n) `int memo[N]; int f(int n) { if(n<=1) { return 1; } f[n] = f(n - 1); return f[n] << 1; }` – kaitian521 May 25 '16 at 14:59
  • Think about, or better yet, write down what calls will be made when you call f (20). – gnasher729 May 25 '16 at 15:22

1 Answers1

0

I think your recursion equation is correct.

But this specific case is easy enough, to "just think" about it a bit without going further into "how to solve recursions in general".

Let's have a look at f(3)

            f(3)           

     f(2)    +    f(2)         

 f(1) + f(1) + f(1) + f(1)

So, how many calls do we have? 1 + 2 + 4

Hmm.. how about f(4)?

                           f(4)

             f(3)           +            f(3)

     f(2)    +    f(2)      +     f(2)     +   f(2)

 f(1) + f(1) + f(1) + f(1)  +  f(1) + f(1) + f(1) + f(1)

So, how many calls do we have? 1 + 2 + 4 + 8

So we can make an educated guess for n=5: 1+2+4+8+16. And if you think about it, it also makes sense because: numCalls(f(5)) = 2*numCalls(f(4)) + 1 (the + 1 stems from the call to f(5) itself).

We can generalize this to 

T(n) = sum(2^i) for i in (0, n-1)

Now, if we use the fact that

sum(2^i) for i in (0, n-1) == 2^n - 1

it becomes very obvious that 

T(n) = 2^n - 1

which is in O(2^n)

Left as an exercise:

Prove by induction that

T(n) = 2*T(n-1) + 1   <=>  T(n)  = 2^n - 1

Or a bit more general:

T(n) = 2*T(n-1) + c   <=>  T(n)  = c*(2^n - 1)

Just as a side-note as suggested in the comments: you can drastically improve perfomance by using memoization

dingalapadum
  • 2,077
  • 2
  • 21
  • 31
  • In case of merge sort we also have 2^N calls? –  May 25 '16 at 17:16
  • @ivan_petrushenko Because you will have less levels!!! Draw the tree for mergesort: it is not the same: you'll go from T(4) directly to T(2). You will skip the T(3) part. The recursion looks similar, but it is crucial that your recursive call works on a problem _half_ the size of the original problem - rather than working with a single element less. – dingalapadum May 25 '16 at 17:22
  • @ivan_petrushenko In mergesort you will get the recursion tree with log(n) levels. Here you get a recursion tree with n levels! That's why you get very different results. Think about T(8). Here you'll go T(8), T(7), T(6), T(5), T(4), T(3), T(2), T(1). In mergesort you'll go T(8), T(4), T(2), T(1). It becomes even clearer if you look at bigger numbers – dingalapadum May 25 '16 at 17:25
  • Here we have a recursion tree with n levels, how do you use this fact? In case of merge sort we multiply logn levels to n. What we should do with n levels in our case? –  May 25 '16 at 17:44
  • @ivan_petrushenko Mergesort: you have log n levels which each costs n. This here you have: n levels and level i costs 2^(i-1). What we do with our n is to sum up over each of those... Not sure if I understood what you are asking. – dingalapadum May 25 '16 at 18:42