Question $3$

Given the following algorithm, MyAlgorithm, analyze what the algorithm does then answer the

questions below.

Algorithm MyAlgorithm$($A$,$ n$)$

Input: Array of integer containing n elements

Output: Possibly modified Array A

done $$ true

j $0$

while j $<=$ n $-2$ do

if A$[$j$]>$ A$[$j $+1]$ then

swap$($A$[$j$],$ A$[$j $+1])$

done:$=$ false

j $$ j $+1$

end while

j $$ n $-1$

while j $>=1$ do

if A$[$j$]<$ A$[$j $-1]$ then

swap$($A$[$j $-1],$ A$[$j$])$

done:$=$ false

j $$ j $-1$

end while

if $$ done

MyAlgorithm$($A$,$ n$)$

else

return A

a$)$ Trace $($hand$-$run$)$ MyAlgorithm for an array A $=(3,10,5,2,1)[$You do not need to show every

single step of the trace$].$ What is the resulting A$?$

b$)$ What is the Big$-$O $($O$($n$))$ and Big$-$Omega $(\backslash$Omega $($n$))$ time complexity for algorithm MyAlgorithm

below in terms of n$?$ Explain how you concluded such complexity.