What is the algorithmic complexity of this recursive function?-CodePudding

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.

CodePudding user response：

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.

CodePudding user response：

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.)