0

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!

misha
  • 1
  • 1
    Hi :) Unfortunately, we have $T(n)\notin O(n^3)$, because the polynomial $r^4 - r^3 - r^2 - 1$ has a real root ($r_0\approx 1.7549$) with absolute value greater than 1. But the time to compute $T(n)$ could be in $O(n^3)$. – Jochen Jun 02 '23 at 07:17
  • Hi, welcome to Math SE. Why do you expect an $n^3$ behaviour? Even if a solution of this recursion relation isn't exponential, it won't be asymptotic to a non-constant monomial because e.g. if the LHS $\sim kn^3$ the RHS $\sim 3kn^3$. (It'd be different if $c$ changed to $cn^3$, or the sum of $T$ coefficients was the same on both sides.) – J.G. Jun 02 '23 at 07:22
  • @Jochen really sorry but i meant O(3^n) not O(n^3), I updated the question, sorry for the confusion. – misha Jun 02 '23 at 07:23
  • That still doesn't work. It needs to be $O(r^n)$ for $r^4-r^3-r^2-1$. Its roots are $-1$, a real between $1$ and $2$, and two complex numbers of modulus $<1$. – J.G. Jun 02 '23 at 07:24
  • Hi :) i think, it's fine, because $O(r^n)\subseteq O(3^n)$ for $r\leq 3$. If $f(n)\leq c\cdot r^n$ for $n\geq N$, then $f(n)\leq c\cdot 3^n$ for $n\geq N$. – Jochen Jun 02 '23 at 07:31
  • Ah, yes, it's $o(3^n)$ ($o(2^n)$, in fact). – J.G. Jun 02 '23 at 07:55

0 Answers0