Big-O of a recursive function called twice based on two variables

Question

What will be the time complexity of this function:

 public int calculate(int n, int i, int c) {
  if(i >= n || c <= 0)
    return 1;

  int p1 = 2 * calculate(n, i, c-1);
  int p2 = 1 + calculate(n, i+1, c);

  return  p1 + p2;
}

The function gets called twice, one for all values of 'c' and one for all values of 'i'. Can we say that its time complexity is O(2^(n+c)) If so, is it possible to find a tighter limit?

My bad, the 'if' condition should have been: if(i >= n || c <= 0) — user1861872, Apr 18 '19 at 12:18
Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Prune, Apr 18 '19 at 16:57

score 0 · Answer 1 · answered Apr 18 '19 at 12:32

0

O(2^(n + c)) is sufficient. I'm not sure how we can get any more granular than that asymptotically. If N has a significantly greater absolute difference from i, than C has from 0, we can just say O(2^n) or O(2^c)

answered Apr 18 '19 at 12:32

Elroy Jetson

938
11
27

Big-O of a recursive function called twice based on two variables

1 Answers1