How do you calculate the time complexity of the recursive tribonacci function F(n) = F(n-1) + F(n-2) + F(n-3) with base cases F(0) = 0, F(1) = F(2) = 1?
Recursive Tribonacci Sequence Time Complexity
Viewed 359
1 Answers
It's easier to use induction to prove it's O(1.84^(n-1)).
T(n) = 1 when n <= 2 and T(n) = T(n-1) + T(n-2) + T(n-3) when n > 2.
Base case:
T(3) = 1 + 1 + 1 = 3
T(3) = 1.84^2 ≈ 3
T(3) = O(1.84^(n-1))
Inductive case: Assume T(n-1) = 1.84^(n-2). Then,
T(n) = T(n-1) + T(n-2) + T(n-3)
T(n) = 1.84^(n-2) + 1.84^(n-3) + 1.84^(n-4)
T(n) ≈ 1.84^(n-1)
T(n) = O(1.84^(n-1))
If you want it to be exact, use the tribonacci constant instead, but it's tedious to show it is equal. However, I can edit this to show it if you want.
Related