I am currently analyzing the time complexity of a recursive function, T(n), defined as T(n) = T(n-1) + T(n-2) + T(n-4) + c, where c is a constant. To prove that the time complexity of T(n) is O(3^n), I am following an example that demonstrates the time complexity of the Fibonacci sequence.
In this example, the Fibonacci sequence is analyzed to show that its time complexity is O(n), and it can be expressed as a recurrence relation using the ratio r. The Fibonacci sequence example can be found at stackabuse
Now, using the recurrence relation r^4 - r^3 - r^2 - 1 = 0 to represent T(n), I would like to prove that the time complexity of T(n) is O(3^n) by following the same principles as the Fibonacci sequence example.
I kindly request assistance in understanding the steps and techniques required to prove the time complexity of T(n) as O(3^n) based on the provided representation and the example given in the link.
Thank you for your valuable help!