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^2)
b. O(2^n)
c. O((1-sqrt 5)/2)^n)
d. O(n)
e. Answer depends on a and b.
f. O((1+sqrt 5)/2)^n)
Solving the Fibonacci sequence I got that:
fib(n)= 1/(sqrt 5) ((1+sqrt 5)/2)^n - 1/(sqrt 5) ((1-sqrt 5)/2)^n
But what would be the time complexity in this case? Would that mean the answers are c and f?
From your closed form of your formula, the term 1 / (sqrt 5) ((1 - sqrt 5) / 2)^n has limit 0 as n grows to infinity (|(1 - sqrt 5) / 2| < 1). Therefore we can ignore this term. Also since in time complexity theory we don't care about muliplication constants the following is true:
fib(n) = Θ(φ^n)
where φ = (1 + sqrt 5) / 2 a.k.a. the golden ratio constant.
So it's an exponential function and we can exclude a, d, e. We can exclude c since as was said it has limit 0. But answer b is also correct because φ < 2 and O expresses an upper bound.
Finally, the correct answers are:
b, f
Θ(φ^n) is correct when a=1 and b=1 or a=1 and b=2 . The value of φ depends on a and b.
For computing fib(n-1) and fib(n-2) if we compute them recursively complexity is exponential, but if we save two last values and use them, complexity is O(n) and not depends on a and b.
