b$.(1$ mark$)$ Consider the call fib $($n$)$ for any n$>=20.$ How many times will fib $($n$-2)$ be called?

Solution:

fib$($n$-2)$ is going to get called F$($n$($n$-2)+1)=$ F$(3)=2.$

fib$($n$)$

fib$($n$-1)$

fib$($n$-2)$

fib$($n$-2)$

fib$($n$-3)$