Question

2.Consider the following algorithm and A is a 2-D array of size ???? × ????: int any_equal(int n, int A[][]) { int i, j, k, m; for(i = 0; i < n; i++) for( j = 0; j < n; j++) for(k = 0; k < n; k++) for(m = 0; m < n; m++) if(A[i][j]==A[k][m] && !(i==k && j==m)) return 1 ; return 0 ; } a. What is the best-case time complexity of the algorithm (assuming n > 1)? b. What is the worst-case time complexity of the algorithm?

Answer 1

Answer:

(a) What is the best case time complexity of the algorithm (assuming n > 1)?

Answer: O(1)

(b) What is the worst case time complexity of the algorithm?

Answer: O(n^4)

Explanation:

(a) In the best case, the if condition will be true, the program will only run once and return so complexity of the algorithm is O(1) .

(b) In the worst case, the program will run n^4 times so complexity of the algorithm is O(n^4).