patternMinor
Fibonacci Sequence recursion algorithm and the time complexity
Viewed 0 times
therecursionfibonaccitimesequencealgorithmandcomplexity
Problem
I am reading a free book on algorithms
http://www.cse.iitd.ernet.in/~Naveen/courses/CSL630/all.pdf
and on page 13 it says
"Compare this to the recurrence relation for Fn: we immediately see that T(n) ≥ Fn"
I do not understand how they know that T(n) ≥ Fn
if someone could explain it to me it would be much appreciated.
here is a picture of the information needed
http://www.cse.iitd.ernet.in/~Naveen/courses/CSL630/all.pdf
and on page 13 it says
"Compare this to the recurrence relation for Fn: we immediately see that T(n) ≥ Fn"
I do not understand how they know that T(n) ≥ Fn
if someone could explain it to me it would be much appreciated.
here is a picture of the information needed
Solution
You can prove that $T(n) \geq F_n$ by induction. For $n = 0$ and $n = 1$ we have $T(n) \geq 1$ and $F_n \leq 1$. Suppose that the claim holds for $n-1$ and $n-2$. Then
$$
T(n) = T(n-1)+T(n-2)+3 \geq F(n-1)+F(n-2) = F(n).
$$
$$
T(n) = T(n-1)+T(n-2)+3 \geq F(n-1)+F(n-2) = F(n).
$$
Context
StackExchange Computer Science Q#81052, answer score: 2
Revisions (0)
No revisions yet.