Time complexity of recursion-tree

Question

What will be the time complexity of a function Fn(n) which recursively calls Fn(1),Fn(2),Fn(3),...,Fn(n-1) to solve Fn(n). Fn(1) =1 is given as base condition. Will it be O(n^n) or less. I think it should be less than O(n^n) but i am not able to find a way to get the correct complexity of this recursion.

recursion tree for Fn(4) would be something like this

              Fn(4)
         /        |     \
      Fn(3)    Fn(2)   Fn(1)
     /   \        /
   Fn(2) Fn(1) Fn(1)
   /
Fn(1)

It will be O(2^n) here is the proof http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence — AnotherGeek, Jun 24 '16 at 12:35

score 6 · Answer 1 · answered Jun 24 '16 at 13:24

The recurrence would look something like this:

T(1) = 1
T(n) = Σ T(i), from i = 1 to n-1

Not particularly helpful at first glance, huh? So Let's break this down into subproblems and see what they look like:

   T(5) = T(4) + T(3) + T(2) + T(1)
=> T(5) = T(4) + T(3) + T(2) + 1

   // The sub problems
   T(4) = T(3) + T(2) + 1
   T(3) = T(2) + 1
   T(2) = 1

Now let's substitute some of these sub problems back into our original problem:

   T(5) = T(4) + T(3) + T(2) + 1
=> T(5) = T(4) + T(4)
=> T(5) = 2T(4)

So we can derive that the recurrence really looks like:

T(n) = 2T(n-1)
T(n-1) = 2T(n-2)

So we can rewrite our recurrence as

T(n) = 2[ 2T(n-2) ]
T(n) = 2[ 2 [ 2T(n-3) ] ]
...
T(n) = 2^k [ T(n-k) ]

Since our base case we've described earlier is

T(1) = 1
// Therefore
n = 1
k = 1
n = k

Now we can substitute at our recurrence for:

   T(n) = 2^n [ T(1) ]
   T(n) = 2^n [ O(1) ]
=> T(n) = 2^n

Therefore, your recurrence is O(2^n)

score 4 · Accepted Answer · answered Jun 24 '16 at 12:54

4

T(F(I)) = T(F(I - 1)) + T(F(I - 1)) + O(1), so it looks like O(2^n).

(Take a look at you recursion tree, T(F(4)) = T(F(3)) + T(F(2)) + T(F(1)) + O(1), while substitute T(F(2)) + T(F(1)) with T(F(3)) you will get T(F(4)) = T(F(3)) + T(F(3)))

answered Jun 24 '16 at 12:54

Shane Lu

1,056
1
12
21

score 0 · Answer 3 · answered Jun 24 '16 at 13:29

We can prove by induction that it is 2^n
First we prove that F(n) = (2^n-1) * F(1)
it is true for n=1 so let's prove this for n+1
F(n+1) = F(n) + F(n-1) + .. + F(1)
=(2^n-1 + 2^n-2 +...+2^0) * F(1)
=((1-2^n)/(1-2)) * F(1) = 2^n * F(1)
So we have the formula and from it the complexity is easy to get

score -3 · Answer 4 · answered Jun 24 '16 at 12:28

-3

Because you memoize, it will be O(n) time. You use O(n) in memory to compensate for it.

answered Jun 24 '16 at 12:28

Jason

86
1
9

if we don't use any table to store result of sub-problems, then what will be the complexity? – Deepankar Singh Jun 24 '16 at 12:31
How? Can you please explain? – Deepankar Singh Jun 24 '16 at 12:31
1

Sounds more like 2^n to me – Henry Jun 24 '16 at 12:34
1

Not sure how to write equations on comments but: g(n) = sum of i=1 to n-1, g(n-1). This will give you g(n-1)+2g(n-2)+3g(n-3).. + ng(n). This roughly goes to n!(g(1)). From an intuitive sense, you can see that you need to calculate g(n-1) always. Since g(n-1) needs to be calculated via g(n-2).. it goes on for ~ n! times. – Jason Jun 24 '16 at 12:37
1

Fn(n) does the work Fn(n-1) has already done (sum of Fn(n-2) ... Fn(1)) plus another Fn(n-1), so is roughly 2 times the work of Fn(n-1) – Henry Jun 24 '16 at 12:41
1

2^n is for Fibonacci. In this case he needs to re-calculate everything to n=1. If he doesn't store anything, which is what the recursion tree looks like (because Fn(4) depends on Fn(3), Fn(2), Fn(1)) he would need to do it n! right? – Jason Jun 24 '16 at 12:42
Just look at the diagram in the question: the right side Fn(4), Fn(2), two times Fn(1) is exactly the same as the subtree rooted at Fn(3). – Henry Jun 24 '16 at 12:45
If he's not using anything to store what he got for Fn(3) Fn(2) Fn(1), shouldn't he need to calculate all those individually? – Jason Jun 24 '16 at 12:46
Sure, but still the effort just doubles. – Henry Jun 24 '16 at 12:49
@Jason O(n!) is making sense, Will think on it. :) – Deepankar Singh Jun 24 '16 at 12:56
DeepankarSingh It seems like everyone is thinking 2^n. So that's probably the right answer. I think it really depends on what you're trying to do with the function. Fibonnaci is 2^n because f(n) = f(n-1) + f(n-2). There are only two subtrees. However from the recurrence diagram you drew there are three subtrees. And this moves towards n! for Fn(n). However, like @Henry was saying the right part of the diagram is the same as subtree at Fn(3). If you don't need to recalculate Fn(3) by doing the whole process of Fn(2) again, then you would have 2^n. However since you are not storing anything – Jason Jun 24 '16 at 13:02
(continued) I'm still like 60% convinced that you have to do it n! times (but then again, I'm a college student and probably wrong :)) . This is because just based on your diagram it looks like you need n-1 subtrees (without substitution and storing prior results) to calculate Fn(n) and each of those need (n-1)-1 subtrees and etc. – Jason Jun 24 '16 at 13:03
@Jason Though i am not using Dynamic programming here, still i need to compute only twice as much as needed for, to compute F(n-1), So that's how complexity turns into 2^n – Deepankar Singh Jun 24 '16 at 13:12
Yeah that's what I figured. – Jason Jun 24 '16 at 13:16

Time complexity of recursion-tree

4 Answers4