Consider the standard recursive Fibonacci number calculation given by the Ruby program:

def Fib$($n$)$

return $1$ if $n==0||n==1$

Fib$(n-1)+$Fib$(n-2)$

end

Therefore, the worst case running time $T(n)$ of Fib$($n$)$ is given by

$T(n)=T(n-1)+T(n-2)$

and $T(0)$ and $T(1)$ have constant run$-$time. What is the most accurate characterization of $T(n)?$

$T(n)=O(n^2)$

$T(n)=(2^n)$

$T(n)=(F_n),$ where $F_n$ is the $n-$th Fibonacci number

$T(n)=O(n)$