HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Fibonacci Sequence recursion algorithm and the time complexity

Submitted by: @import:stackexchange-cs··
0
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

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).
$$

Context

StackExchange Computer Science Q#81052, answer score: 2

Revisions (0)

No revisions yet.