5
$\begingroup$

There's a formula given $$ T(m,n) = \left\{ \begin{array}{l l} 1 & \quad \text{if $m=0$}\\ 1+T(n \mod m, m) & \quad \text{if $m>0$} \end{array} \right.$$ We're told to use repeated substitution to make a conjecture about a closed form for $T(F(n),F(n+1))$, where $F(k)$ is the $k^{th}$ Fibonacci number.This is a practice question and I have no idea how to start. Could someone help?

$\endgroup$
  • 2
    $\begingroup$ You can start by following the advice. What is $T(F(n),F(n+1))$ equal to according to the formula? $\endgroup$ – Yuval Filmus Dec 2 '14 at 1:42
  • 2
    $\begingroup$ The worst case for the euclidean algorithm could find out started with (1,1) and iterate reversing euclidean algorithm always in each step put de minimum quotation $q = 1$, and there appears Fibonacci numbers in the residues. $\endgroup$ – jonaprieto Dec 7 '14 at 4:57
2
$\begingroup$

For $F_0 = 0, F_1 = F_2=1, \dotsc$ consider

$$ \begin{align} T(F_n, F_{n+1}) &= 1+T(F_{n+1}\mod{F_n}, F_n) & \text{by definition}\\ &= 1+T(F_{n-1}\mod{F_n}, F_n) & \text{since }F_{n+1} = F_n+F_{n-1}\\ &= 1+T(F_{n-1}, F_n) & \text{since }F_{n-1} \le F_n\\ \end{align} $$ continuing, we see $$ \begin{align} T(F_n, F_{n+1}) &= 1+T(F_{n-1}, F_n)\\ & = 2 +T(F_{n-2}, F_{n-1})\\ & = 3 +T(F_{n-3}, F_{n-2}) \end{align} $$ and in general $$ T(F_n, F_{n+1}) = k+T(F_{n-k}, F_{n-k+1}) $$ so when $k=n$ we have $$ T(F_n, F_{n+1}) = n+T(F_0, F_1) = n+T(0, 1) = n+1 $$ Now to make a conjecture about the growth of $T(F_n, F_{n+1})$ we need to find how large $n+1$, the run time, will be in terms of the size of $F_{n+1}$. There is a closed form for this, namely $$ F_k = \frac{\phi^k-\psi^k}{\sqrt{5}} $$ where $\phi = (1+\sqrt 5)/2\approx1.618$ and $\psi = (1-\sqrt 5)/2\approx-0.618$. Since $|\psi|<1$ that term will be negligible for sufficiently large values of $k$ so we have $F_k\approx \phi^k/\sqrt5$. Taking the log (to the base $\phi$) of both sides, we have $\log{F_k}\approx k-\log{\sqrt5}$, so $k$ will be $\log {F_k}$ plus a constant which we can ignore. In terms, then, of its arguments, $p, q$, with $q \ge p$ we'll have our conjecture: $$ T(p, q) = O(\log q) $$ which happens to be true, even if we don't restrict ourselves to Fibonacci numbers for the arguments.

This function is just the timing function for the Euclidean algorithm, which finds the greatest common divisor of the arguments:

gcd(p, q) =
   if p = 0
      return q
   else
      return gcd(q mod p, p)

For instance, $$ \gcd(15, 24) = \gcd(9, 15) = \gcd(6, 9) = \gcd(3, 6) = \gcd(0, 3) = 3 $$ after five recursive calls. It happens that the longest this algorithm will take to complete is when the arguments are consecutive Fibonacci numbers. The upshot is that, fortunately for us this is fast, being no worse than proportional to the number of digits in the arguments.

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