Consider the memoized Fibonacci number calculation given by the Ruby program:

@mem $=[0,1]$

def fib$\_$mem$($n$)$

@mem$[$n$]$ I$|=$ fib$\_$mem$($n$-1)+$ fib$\_$mem$($n$-2)$

end

What is the worst case running time $T(n)$ of fib$\_$mem$($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)$