1
$\begingroup$

We will see in Chapter 1 that the addition of two n-bit numbers takes time roughly proportional to n; this is not too hard to understand if you think back to the gradeschool procedure for addition, which works on one digit at a time. Thus fib1, which performs about Fn additions, actually uses a number of basic steps roughly proportional to nFn. Likewise, the number of steps taken by fib2 is proportional to n^2, still polynomial in n and therefore exponentially superior to fib1. This correction to the running time analysis does not diminish our breakthrough.

I'm confused on how we know fib1, which is the recursive fibonacci algorithm, performs about Fn additions. Kindly if someone could help explain.

$\endgroup$
2
  • $\begingroup$ Draw the recursive call tree. How many nodes are there in the left and right subtree of node $n$? Do induction. $\endgroup$
    – Pål GD
    Commented May 11 at 22:29
  • $\begingroup$ Sorry, I'm not sure how to find the number of nodes in the right and left subtree of node n. Also, now that I looked into it, in Rosen's Discrete Math book they very briefly (like 1 sentence lol) mention that the number of additions is $F_{n+1} - 1$ (leaving as an exercise for the reader) instead of $F_{n}$. I think I did the strong induction part correct for the $F_{n+1} - 1$, but not sure how we can approximate to $F_{n}$. Additionally, I was looking more for a derivation rather than just inductive verification. $\endgroup$
    – Bob Marley
    Commented May 12 at 1:59

1 Answer 1

1
$\begingroup$

Look at the definition of fib1. It computes one addition in this call, namely fib1(n-1) + fib1(n-2) and then some additions in the recursive calls.

We will prove that the total number of additions performed when calling fib1(n) is exactly $F_n-1$.

Define fib1(0) = fib1(1) = 1, and otherwise fib1(n) = fib1(n-1) + fib1(n-2).

We proceed by induction. The base cases are $n \leq 1$. There, no addition is performed, and hence they are both equal to $F_0 - 1 = F_1-1$.

Induction hypothesis: it holds for all values below $n$.

It follows from the definition that the number of additions in fib1(n) = fib(n-1) + fib(n-2) is 1 plus the recursive calls, and by the induction hypothesis, this is $1 + F_{n-1} -1 + F_{n-2}-1 = F_n-1$.

The claim follows.

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