CODEWITHSUNDEEP
time-complexity
Diana
Diana

Reputation: 1437

Fibonacci Sequence - Time Complexity

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?

Upvotes: 2

Views: 337

Answers (2)

Meysam Ghahramani
Meysam Ghahramani

Reputation: 169

Θ(φ^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.

Upvotes: 1

JuniorCompressor
JuniorCompressor

Reputation: 20025

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

Upvotes: 3

Related Questions