What is the asymptotic complexity of the following functions? Justify your answer.

i$)$

def fun$1($n$)$:

sum $=0$;

if $($n $<1)$:

return $1$

else:

sum $=$ sum $+$ fun$1($n $-1)$

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

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

sum $+=$ i

return sum

Recurrence Relation:

Complexity in Big$-$Oh:

ii$)$

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

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

return $1$

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

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

elif:

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

Recurrence Relation:

Complexity in Big$-$Oh:

iii$)$ Assume $$combineAll$()$ is O$($n$)$ where n is $$right$-$left$.$

def fun$3($a$,$ left, right$)$:

if left $==$ right:

if a$[$left$]>0$:

return a$[$left$]$

else:

return $0$

center $=$ int$(($left $+$ right$)/2)$

caseLeft $=$ fun$3($a$,$ left, center$)$

caseRight $=$ fun$3($a$,$ center$+1,$ right$)$

caseLR $=$ fun$3($a$,($left$+$center$)//2,($center$+$right$)//2)$

combineAll$($caseLeft$,$ caseRight, caseLR$)$ # Assume it is O$($n$)$

Recurrence Relation:

Complexity in Big$-$Oh: