For the following program fragments, give an analysis of the running time $($using $)$

i$)$

i $=1$

sum $=0$

while i $<$ n$*$n:

sum$+=1$

i $+=3$

i$)$

i $=1$

sum $=0$

while i $<$ n$*$n:

sum$+=1$

i $*=3$

ii$)$

k $=1$

n $=$ n $*$ k

if n $<10$:

k $=$ n

else:

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

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

iii$)$

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

for j in range$($i$*2,$ n$**3)$:

if j $>$ i:

for k in range$($n$**2)$:

sum$+=1$

iv$)$

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

for j in range$($i$*2,$ n$**3)$:

if j $<$ i:

for k in range$($n$**2)$:

sum$+=1$

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: