Time complexity of a recursive function with three recursive calls

Question

What will be the time complexity of a recursive function with the following recurrence relation:

T(n) = T(n-1) + T(n-2) + T(n-3), T(0) = T(1) = 1 and T(2) = 2

I know that a function with two recursive calls will give us an exponential time complexity of O(2^n), would this mean that the function with the above recurrence relation will have the time complexity of O(3^n)?

Thanks for the help.

Answer 1

To be more specific suppose that you have a function like:

T(n) = T(n-1) + T(n-1) + T(n-1), T(0) = 1

The way that this is written The time complexity is exactly O(3^n).

Your function is a little bit better than this function but still the time complexity is the same O(3^n)

Now if we rewrite my proposed code like:

T(n) = 3 * T(n-1), T(0) = 1

The the complexity is just O(n)! because the results of the previous calls are reused without being called again.

So in your implementation if you can have buffer to not call but just use the previously called values (some languages actually can support this) then the complexity will degrade to O(n).