Consider the following functions which both take as arguments three n-element arrays A, B, and C:...

Transcribed Image Text:

Consider the following functions which both take as arguments three n-element arrays A, B, and C: COMPARE-1(A, B, C) For i = 1 to n For j = 1 to n If A[i] + Ci]B[j] Return FALSE Return TRUE COMPARE-2(A, B, C) auxA[1]+C[1] For i = 2 to n If A[i] + C[i]> aux Then aux := A[i] + C[i] For j = 1 to n If aux B] Return FALSE Return TRUE (a) When do these two functions return TRUE? (b) What is the worst-case running time for each function? Consider the following functions which both take as arguments three n-element arrays A, B, and C: COMPARE-1(A, B, C) For i = 1 to n For j = 1 to n If A[i] + Ci]B[j] Return FALSE Return TRUE COMPARE-2(A, B, C) auxA[1]+C[1] For i = 2 to n If A[i] + C[i]> aux Then aux := A[i] + C[i] For j = 1 to n If aux B] Return FALSE Return TRUE (a) When do these two functions return TRUE? (b) What is the worst-case running time for each function?

Answer rating: 100% (QA)

a Both functions return TRUE when for all elements i in the a... View the full answer