1

I have the following recursive Python function:

def f(n):
    if n <=2:
        result = n
    else:
        result = f(n-2) + f(n-3)
    return result

What would you say is the algorithmic complexity of it?

I was thinking this function is really similar to the Fibonacci recursive function which has a complexity of O(2^N) but I am not sure if that would be correct for this specific case.

tilman151
  • 563
  • 1
  • 10
  • 20
Booker
  • 11
  • 1
  • 5
    Please update the indentation of your code. Python is very sensitive to indentation, as are python programmers. – quamrana Dec 08 '22 at 14:20
  • 1
    This looks exactly like a fibonacci recursive implementation. Please check this answer: https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence – Vame Dec 08 '22 at 14:24
  • 2
    It's not exactly the same. You reach the base cases faster (though not fast enough, I believe, to avoid exponential growth; it's just *slower* exponential growth). – chepner Dec 08 '22 at 14:25
  • Exactly, I think it's similar to the Fibonacci recursive implementation but not the same as the base case is reached faster for this function (the recursive sequence is being substracted by higher numbers than Fibonacci). I do think it's exponential as well just with a smaller base as mentioned in the answer below. – Booker Dec 08 '22 at 17:23

2 Answers2

1

Just write the complexity function.

Assuming all atomic operations here worth 1 (they are O(1), so, even if it is false to say that they are all equal, as long as we just need the big-O of our complexity, at the end, it is equivalent to the reality), the complexity function is

def complexity(n):
    if n<=2:
        return 1
    else:
        return 1 + complexity(n-2) + complexity(n-3)

So, complexity of f computation is almost the same thing as f!

Which is not surprising: the only possible direct return value for f is 2. All other values are sum of other f. And in absence of any mechanism to avoid to recompute redundant value, you can say that if f(1000) = 2354964531714, then it took 2354964531714/2 addition of f(?)=2 to get to that result.

So, number of additions to compute f(n) is O(f(n)) And since f(n) is O(1.32ⁿ) (f(n)/1.32ⁿ → ∞, while f(n)/1.33ⁿ → 0. So it is exponential, with a base somewhere in between 1.32 and 1.33), it is an exponential complexity.

chrslg
  • 9,023
  • 5
  • 17
  • 31
0

Let's suppose, guessing wildly, that T(n) ~ rT(n-1) for large values of n. Then our recurrence relation...

T(n) = c + T(n-2) + T(n-3)

Can be rewritten...

r^3T(n-3) ~ c + rT(n-3) + T(n-3)

Letting x = T(n-3), we have

(r^3)x ~ c + rx + x

Rearranging, we get

x(r^3 - r - 1) ~ c

And finally:

r^3 - r - 1 ~ c/x

Assuming again that x is very large, c/x ~ 0, so

r^3 - r - 1 ~ 0

I didn't have much look solving this analytically, however, as chrslg finds and Wolfram Alpha confirms, this has a root around ~1.32-1.33, and so there is real value of r that works; and so the time complexity is bounded by an exponential function with that base. If I am able to find an analytical solution, I will post with details (or if anybody else can do it, please leave it here.)

Patrick87
  • 27,682
  • 3
  • 38
  • 73
  • without going into too much detail, using the method at this page: https://math.stackexchange.com/questions/2838797/is-there-really-analytic-solution-to-cubic-equation, I derived this closed-form expression for a root, which has the right approximate value: cbrt(1/2+sqrt(1/4-1/27)) + 1/(3cbrt(1/2+sqrt(1/4-1/27))) ... note that cbrt is the cube root and sqrt is the square root. – Patrick87 Dec 12 '22 at 19:39