3. For each of the following algorithms, analyze the worst-case running time. You should give your answer in big-Oh notation. You do not need to give an input which achieves your worst-case bound, but you should try to give as tight a bound as possible. Justify your answer (show your work). This likely means discussing the number of atomic operations in each line, and how many times it runs, writing out a formal summation for the runtime complexity T(n) of each algorithm, and then simplifying your summation. (a) 1 f(A): // A is a square, 2D array; indexed starting from 1 2 let d be a copy of A 3 for i = 1 to len(A): 4 d[i][i] = 0 5 6 for i = 1 to len(A): 7 for j = 1 to len(A): 8 for k = 1 to len(A): 9 if (d[i][k] + d[k][j])

(b) 1 g(A): // A is a list of integers 2 for i = 1 to len(A): 3 for j = 1 to len(A)-i: 4 if A[j+1] > A[j]: 5 // swap A[j+1] and A[j] 6 tmp = A[j+1] 7 A[j+1] = A[j] 8 A[j] = tmp 9 return A

(c) Here, abs(n) returns the absolute value of its argument, and can be treated as an atomic operation 1 h(A): // A is a list of integers, of length at least 2, first index is 1 2 min = abs(A[1] - A[2]) 3 for i = 1 to len(A): 4 for j = i+1 to len(A): 5 if abs(A[i] - A[j])

3. For each of the following algorithms, analyze the worst-case running time. You should give your answer in big-Oh notation. You do not need to give an input which achieves your worst-case bound, but you should try to give as tight a bound as possible. Justify your answer (show your work). This likely means discussing the number of atomic operations in each line, and how many times it runs, writing out a formal summation for the runtime complerity Tn) of each algorithm, and then simplifying your summation. (a) 1 f(A): // A is a square, 2D array; indexed starting from 1 let d be a copy of A for i = 1 to len (A): d[i] [i] = 0 for i = 1 to len(A): for j = 1 to len(A): for k = 1 to len(A): if (d[i] [k] + d[k] [j]) A[j]: // swap A [j+1] and A[j] tmp = A[j+1] A[j+1] = A[j] A[j] = tmp 9 return A 600 O (c) Here, abs(n) returns the absolute value of its argument, and can be treated as an atomic operation 1 h(A): // A is a list of integers, of length at least 2, first index is 1 2 min = abs(A[1] - A[2]) 3 for i = 1 to len(A): for j = i+1 to len(A): if abs (A[i] - A[j])