Consider the following code: int fib $($int x$)\{$ if $(($x $==0))\{$ return$($x$)$; else $\{$ return $($fib $($x $-1)+$ fib $($x $-2))$: i$)$ Write down the recurrence relation of this algorithmin the worst$-$case.$[3]$ i$)$ Solve the recurrence you generated in $($i$)$ using the substitution method to getthe closed$-$form expression of the recurrence.You should show all your work.Any justification that you provide will help when assigning partial marks $[12]$