public int fibonacci$($int n$)\{$

if $($n $<=1)$ return n;

else return fibonacci$($n$-1)+$ fibonacci$($n$-2)$;

$\}$

What is the time complexity of this code snippet?

Note $^$ means raised to the power. For example n$^3$ means n cubed.

Question $29$ options:

O$(2^$n$)$

O$($n$)$

O$($n$^2)$

O$($n log n$)$