Question

How many additions are used by the recursive and iterative algorithms given in Algorithm 7 and 8, respectively, to find the Fibonacci number${\mathbf{f}}_{\mathbf{7}}$ ?

Short answer

Algorithm 7 will do 20 additions and algorithm 8 will do 7 additions.

Step-by-step solution

Algorithms 7 and 8

Algorithm 7 is given as,

Procedure Fibonacci ( n : nonnegative integer)

If n = 0 then return 0

Else if n = 1then return 1

Else return Fibonacci fibonacci (n - 1) + fibonacci (n - 2)

{Output is fibonacci (n) }.

Algorithm 8 is given as:

Procedure iterative Fibonacci (n : nonnegative integer)

If n = 0 then return 0

Else

x : = 0

y : = 1

For i : = 0 to n - 1

z : = x + y

y : = z

Return y

{Output is nth the Fibonacci number}.

Finding the number of addition in algorithm 7 to find the Fibonacci number f7

Aim: To find the Fibonacci number.

By using Algorithm 7,

$\begin{array}{r}{\mathrm{f}}_7={\mathrm{f}}_6+{\mathrm{f}}_5\\ ={\mathrm{f}}_5+{\mathrm{f}}_4+{\mathrm{f}}_4+{\mathrm{f}}_3\\ ={\mathrm{f}}_4+{\mathrm{f}}_3+2{\mathrm{f}}_3+2{\mathrm{f}}_2+{\mathrm{f}}_2+{\mathrm{f}}_1\\ ={\mathrm{f}}_4+3{\mathrm{f}}_3+3{\mathrm{f}}_2+{\mathrm{f}}_1\end{array}$

Further simplified as,

$\begin{array}{r}{\mathrm{f}}_7={\mathrm{f}}_3+{\mathrm{f}}_2+3{\mathrm{f}}_3+3{\mathrm{f}}_2+{\mathrm{f}}_1\\ =4{\mathrm{f}}_3+4{\mathrm{f}}_2+{\mathrm{f}}_1\\ =4\left({\mathrm{f}}_2+{\mathrm{f}}_1\right)+4\left({\mathrm{f}}_1+{\mathrm{f}}_0\right)+{\mathrm{f}}_1\\ =4{\mathrm{f}}_2+9{\mathrm{f}}_1+4{\mathrm{f}}_0\\ {\mathrm{f}}_7=4\left({\mathrm{f}}_1+{\mathrm{f}}_0\right)+9{\mathrm{f}}_1+4{\mathrm{f}}_0\\ =13{\mathrm{f}}_1+8{\mathrm{f}}_0\end{array}$

So, there are 21 terms.

Therefore, Algorithm 7 will do 20 addition.

Finding the number of addition in algorithm 8 to find the Fibonacci number f7

Now, algorithm 8 is an iterative process.

So, to find $f_7$, we have to create the loop at least 7 times.

Therefore, Algorithm 8 will do 7 addition.

Hence, algorithm 7 will do 20 addition and algorithm 8 will do 7 addition.