What is the time complexity of this recursive algorithm?

Question

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

My thinking is: in every recursion we have an addition operation. And we do this operation every time we divide the recursion into two. So I am not sure if I should call it O(N2^N) or O(2^N). I think that O(N2^N) makes more sense since we are dividing the problem into 2^N pieces and adding them separately. Still though I am unsure. So can someone guide me through by showing their steps?

As it stands, it's exponential, but you can easily change it to linear by calculating the value of func3(n-1) just once, i.e. tmp = func3(n-1); return tmp+tmp, or just return 2*func3(n-1) — tobias_k
– tobias_k, Commented Mar 6, 2018 at 11:33
We don't know the time complexity of func3, since you don't define it. That being said, why do you not just return 2 * func3(n-1)? — user3483203
– user3483203, Commented Mar 6, 2018 at 11:34
n = 1: 1 call, n = 2: 2 calls, n = 3: 4 calls, n = 4: 8 calls etc - O(2^N) — Alex Salauyou
– Alex Salauyou, Commented Mar 6, 2018 at 11:38
@AlexSalauyou I see, but should we also not consider the addition progress? — Huzo
– Huzo, Commented Mar 6, 2018 at 11:39

Pavel · Accepted Answer · 2018-03-06 11:41:17Z

2

You can draw the calls to your functions as a binary tree:

    func3
     /\
 func3 func3
.............

You will have n levels of nodes in your binary tree, each next_level_node_count = perv_level_node_count * 2.

That's a geometric progression.

answered Mar 6, 2018 at 11:41

Pavel

1

Sign up to request clarification or add additional context in comments.

Comments

arunk2 · Accepted Answer · 2018-03-07 05:21:11Z

1

Another approach is to form a recurrence equation for the function and solve it. The given function can be represented as

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

When you expand the recurrence as below, we get T(n) = 2^n

T(n) = 2 * { 2 * T(n-2) } = 2^2 * T(n-2)
   = 2^3 * T(n-3)
   = 2^(n-1) * T(n-(n-1))
   = 2^(n-1) * O(1)
   = 2^(n-1)
   = 2^n

Hope it helps!

answered Mar 7, 2018 at 5:21

arunk2

2,4563 gold badges25 silver badges35 bronze badges

Collectives™ on Stack Overflow

What is the time complexity of this recursive algorithm?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related