Derive the cost function for the algorithm, sttate the complexity of the algorithm in Big-Oh, and prove that the derived cost function is in the stated order (big-Oh).

1a)

for i = 1 ... n

for j = i ... 1

if vals[i] >= vals[i-1]

break

v = vals[i]

vals[i] = vals[i-1]

vals[i-1] = v

return vals

1b)

C = Array[n][n]

for i = 0 ... n

C[i,0] = 0

C[0,i] = 0

for i = 1 ... n

for j = 1 ... n

if X[i] == Y[j]

C[i,j] = C[i-1,j-1] + 1

else if C[i,j-1] < C[i-1,j]

C[i,j] = C[i-1,j]

else

C[i,j] = C[i,j-1]

return C[n,n]

1c)

acc = X
for i =	2	... sqrt( X )
count	=	0
while	acc		% i == 0
acc	= acc / i
count =			count + 1

if count > 0

print i (count)