CSE $2331$ Homework $3$

Spring, $2024$

Write a recurrence relation describing the WORST case running time of each of the following algorithms and determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution using either expansion into series $($substitution$)$ or a recursion tree. You may NOT use the Master theorem. Assume that all arithmetic operations take constant time.

Simplify and express your answer as $(n^k)$ or $(n^k(lo{g}_{2}n))$ wherever possible. If the algorithm takes exponential time, then just give exponential lower bounds.

WRITE YOUR ANSWERS ON A SEPARATE SHEET$/$FILE$.$

DO NOT SUBMIT A MARKED UP QUESTION SHEET$/$FILE$.$

$1.$

func$1(A,n)$

$\frac{?}{{?}^{**}A}=$ array of $n$ integers

if $)(40$ then return $A[n]$

for ilarr$1$ to ${|}_{{?}_{?}}\frac{n}{2_{{?}_{?}}}|$ do

for jlarr$1$ to ${|}_{{?}_{?}}lo{g}_6(n{)}_{{?}_{?}}|$ do

$A[i+j]larrA[i]-A[j]$

end

end

xlarrfunc$1(A,n-9)$

return $(x)$;

$2.$

func $2(A,n)$

$\frac{?}{{?}^{**}A}=$ array of $n$ integers

if $)(20$ then return $A[n]$;

$2$xlarr$0$;

$3$ for ilarr$1$ to $5$ do

$4$ for jlarr$1$ to $n-3$ do

$5,A[j]larrA[j]-A[j+1]$;

$6$ end

$/*$ Note: This recursive call in inside the for loop that starts in step $3.$

$7,$xlarrx$+$func$2(A,{|}_{{?}_{?}}\frac{n}{5_{{?}_{?}}}|)$;

$8$ end

$9$ return $(x)$;