CODEWITHSUNDEEP
recursionbig-o
D. Phi
D. Phi

Reputation: 625

What is the runtime of this recursive code?

I am wondering what the runtime for the following recursive function would be: 

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

If you think of it as a call tree, each node would have 2 branches. The number of nodes in that call tree would be 2⁰ + 2¹ + 2² + 2³ + ... + 2^n which is equivalent to 2^(n+1) - 1. So the time complexity of this function should be O(2^(n+1)-1) assuming that each call has a constant time of O(1) - Am I correct?. According to the book where I have this example from, the time complexity is O(2^n). I am confused - what am I missing?

Upvotes: 0

Views: 62

Answers (1)

DPenner1
DPenner1

Reputation: 10452

Big-O Notation ignores constant factors and lower order terms. So O(2^(n+1)-1) is equivalent to O(2^n).

O(2^(n+1)-1) = O(2^n * 2^1 - 1)

We drop the constant factor of 2^1, and then we drop the lower order term of -1 as 2^n grows asymptotically faster.

Upvotes: 1

Related Questions