4
$\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$
4
  • 1
    $\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, 2017 at 19:12
  • 1
    $\begingroup$ @cmptUser Not much better, no. Now there's far too much material. $\endgroup$ Sep 9, 2017 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, 2017 at 20:37
  • $\begingroup$ The PDF link is broken. $\endgroup$
    – user16034
    Jul 10, 2023 at 9:02

5 Answers 5

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, 2017 at 22:54
  • $\begingroup$ Yes, that's what the text mean. $\endgroup$
    – Daniel
    Sep 9, 2017 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$
1
$\begingroup$

Lemma: For all $c\ge\log_2\Big(\dfrac{1+\sqrt{5}}{2}\Big)\approx 0.6942$ we have $F_n\le 2^{cn}$ for all $n\ge 0$


Since $T(n-1)\ge T(n-2)$ we have, $$ T(n)=T(n-1)+T(n-2)+3\ge 2T(n-1)+3\\ T(n-1)\ge 2T(n-2)+3\\ T(n-2)\ge 2T(n-3)+3\\ \vdots $$ Therefore, \begin{align} T(n)&\ge 2T(n-1)+3\ge 2\big[2T(n-2)+3\big]+3=4T(n-2)+9\\ &\ge 4\big[2T(n-3)+3\big]+9=8T(n-3)+21\\ &\ge 2^iT(n-i)+3(2^i-1) \end{align} Let's take $i=n$ and using lemma, $$ T(n)\ge 2^nT(0)+3(2^n-1)=4.2^n-3\ge 2^{n}\ge 2^{0.6942n}\ge F_n\\ \implies\boxed{T(n)\ge F_n} $$

$\endgroup$
4
  • $\begingroup$ The recurrence is of the second order, so the solution has two degrees of freedom, say $T(0)$ and $T(1)$. $\endgroup$
    – user16034
    Jul 10, 2023 at 9:13
  • $\begingroup$ @YvesDaoust How do you mean? $\endgroup$
    – Sooraj S
    Jul 10, 2023 at 9:46
  • $\begingroup$ @YvesDaoust i mean could you please explain a bit more ? $\endgroup$
    – Sooraj S
    Jul 10, 2023 at 9:52
  • $\begingroup$ There must be a $T(1)$. $\endgroup$
    – user16034
    Jul 10, 2023 at 10:02
1
$\begingroup$

The simplest way to see that $T(n) \geq f(n)$ is to note that in the definition of the function, the only two values explicitly defined are $f(0) = 0$ and $f(1) = 1.$ All the rest are defined by adding two values together. Since the only explicitly defined, non-zero value is $f(1) = 1,$ we see at least $f(n)$ additions are required, giving $T(n) \geq f(n)$ immediately.

$\endgroup$
0
$\begingroup$

$$T(n)=T(n-1)+T(n-2)+a$$ is a linear recurrence with constant coefficients, and its solution is obtained as usual by combining

  • the general solution of the homogenous equation

$$T_h(n)=T_h(n-1)+T_h(n-2),$$ which is the Fibonacci recurrence, and

  • a particular solution of the non-homogeneous equation, in this case the constant $-a$:

$$-a=-a-a+a.$$

Hence

$$T(n)= c_+\phi^n+c_-(-\phi)^{-n}-a,$$ which grows as fast as the Fibonacci sequence.


Strictly speaking, it is wrong to say $T(n)\ge F(n)$, unless this is justified by the initial conditions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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