For each of the following program fragments, give an analysis of the running time and recurrence relation.

def fun$1($x$,$ y$)$ :

$$if $($x $==0)$ :

$$return y

$$else :

$$return fun$1($x $-1,$ x $+$ y$)$

def fun$1($n$)$:

$$if$($n $==1)$:

$$return $0$

$$else:

$$return $1+$ fun$1($n$//2)$

def$$ fun$1($n$)$:

$$i $=0$

$$if $($n $>1)$:

$$fun$1($n $-1)$

$$for i in range$($n$)$:

$$print$("*",$end$="")$

def fun$($ a$,$ n$)$:

$$if$($n $==1)$:

$$return a$[0]$

$$else:

$$x $=$ fun$($a$,$ n $-1)$

$$if$($x $>$ a$[$n $-1])$:

$$return x

$$else:

$$return a$[$n $-1]$

def fun$($a$,$ b$)$:

$$if $($b $==0)$:

$$return $1$

$$if $($b $\%2==0)$:

$$return fun$($a$*$a$,$ b$//2)$

$$ return fun$($a$*$a$,$ b$//2)*$a

def fun$($n$)$:

$$if$($n $>0)$:

$$fun$($n $-1)$

$$print$($n$,$ end$="")$

$$fun$($n $-1)$