Given that fib(n)=fib(n-1)+fib(n-2) for n>1 and given that fib(0)=a, fib(1)=b (some a, b >0)

Question

Given that fib$(n)$=fib$(n-1)$+fib$(n-2)$ for $n>1$ and given that fib$(0)=a,$ fib$(1)=b$ $($some $a, b >0)$ which of the following is true?

fib$(n)$ is :

Select one or more:

a. $O(n)$

b. $O(n^2)$

c. $O(2^n)$

d. Answer depends on $a$ and $b$.

e. $O(({1 + \sqrt 5}/2)^n)$

f. $O(({1 - \sqrt 5}/2)^n)$

Here what I think,

fib$(2) = (a) + (b) = a + b$

fib$(3) = (a + b) + (b) = a + 2b$

fib$(4) = (a + b + b) + (a + b) = 2a + 3b$

fib$(5) = (a + b + b + a + b) + ( a + b + b) = 3a + 5b$

fib$(6) = 5a + 8b$

fib$(7) = 8a + 13b$

How exactly do I generalize in terms of $n$, so that I can find out the Worst case?

Answer 1

The Time complexity of $fib(n)$ is asymptotically the same as value of $fib(n)$, because $T(fib(n))=T(fib(n-1))+T(fib(n-2))$, so you can create a generating polynomial for it, and see that the right answer is e.

Answer 2

From the values of fib(2) - fib(7) it can be seen that the coefficients are the Fibonacci numbers, $F_{n}$. In fact $fib(n) = F_{n-1} a + F_{n} b$. The Fibonacci numbers have the form \begin{align} F_{n} = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^{n} - \left( \frac{1-\sqrt{5}}{2} \right)^{n} \right]. \end{align} Since $1 + \sqrt{5} > 1 - \sqrt{5}$ then \begin{align} fib(n) \sim \mathcal{O}\left\{\left(\frac{1 + \sqrt{5}}{2}\right)^{n} \right\} \end{align}