Question

This example followed from a Fibonacci algorithm in class. The professor showed us how to compute $T(n) = T(n-1) + T(n-2) + 3$, but left this step for us to prove, so I decided to attempt to prove it! But I am finding it difficult to fully understand how to prove things involving lower and upper-bounds. After looking up many resources including some things from Stanford, this is what I have been able to come up with:

Let $T(n) =$ time for $fib1(n)$, where $T(n) = T(n-1) + T(n-2) + 3$

Claim: For $n \ge 6$, the running time of $fib1(n)$ is exponential, i.e $T(n) \ge (1.41)^n$

Base Case: $$T(6) = 8 \ge (1.41)^6 = 7.86$$ $$T(7) = 13 \ge (1.41)^7 = 11.08$$

Inductive Hypothesis: Assume that for an arbitrary n, $T(n) \ge (1.41)^n$

Prove $T(n+1) \ge (1.41)^{n+1}$: $$T(n+2) = T(n+1) + T(n) + 3$$ $$\ge 1.41^n + 1.41^{n+1} \text{ [By the I.H]}$$ $$ = (1.41^n)(1+ 1.41) > 1.41(1.41)^n$$

Thus, the running time of $fib1(n)$ is $\Omega{(1.41^n)}$

Edit:

I'm not entirely sure how correct this is, but I'm not as worried about that. My main concern is in the induction step, I feel like there is something I am missing conceptually. Specifically, how exactly can we be sure that $$T(n+2) = T(n+1) + T(n) + 3 \ge 1.41^n + 1.41^{n+1} $$ if we only know that $$T(n) \ge 1.41^n$$

I hope this clarifies my question. Thanks!

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top