Question $2$

The following is an improved implementation of the fibonacci number:

def fibonacci $(n)$ :

if $n1$ :

return $(n,0)$

else:

$(a,b)=$ fibonacci $(n-1)$

return $(a+b,a)$

Which of the followings describes the running time behavior of this algorithm?

quadratic

exponential

constant

linear