2
$\begingroup$

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

enter image description here

$\endgroup$
3
  • $\begingroup$ Thank you for the response, we discourage the image content, because it is not searchable, but yes, it is better text > image > link. $\endgroup$ – Evil Sep 9 '17 at 19:12
  • 1
    $\begingroup$ @cmptUser Not much better, no. Now there's far too much material. $\endgroup$ – David Richerby Sep 9 '17 at 20:07
  • $\begingroup$ It's kinda weird, that this algorithm is called bad, because exponentiation takes exponential amount of resources. $\endgroup$ – rus9384 Sep 9 '17 at 20:37
1
$\begingroup$

It's "explained" in t(n) formula you're adding 3 to each "passage" so it will always be greater than f(n). That's because the number of steps for finding f(n) has the same growth of f(n).
Starting from the first numbers Tn is greater than fn.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks for the reply, but just to make sure i understand, what we are doing is comparing the recurrence relations. So we are saying that t(n-1) + t (n-2) + 3 >= f(n-1) + f(n-2) $\endgroup$ – cmptUser Sep 9 '17 at 22:54
  • $\begingroup$ Yes, that's what the text mean. $\endgroup$ – Daniel Sep 9 '17 at 23:00
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.