Consider the following algorithms. int add-them (int n, int A[]) { index i,j,k; j=0; for (i...

  

Transcribed Image Text:

Consider the following algorithms. int add-them (int n, int A[]) { index i,j,k; j=0; for (i 1; in; i++) j=j+A: k=1; for (i=1;i; i++) k=k+k; return j+k; } int any equal (int n, int A[ ][ ]) { index i,j,k,m; for (i=1;in i++) for (j=1:j j++) for (k=1; kn; k++) for (m =1: mmm++) if (AA[k][m] && !(i == k &&j==m)) return 1; return 0; Note: The array parameter A[][] in any equal is an n x n two-dimensional array. For example, when n 5, then A is a 5 x 5 two-dimensional array. (a) Let's say that the basic operation of any equal is the evaluation of the if-statement, ie.. if (A[i][j]==A[k][m] && !(i==k&&j==m)) What is the worst-case time complexity of any equal when A is an n x n two-dimensional array? (b) Draw an example of a two-dimensional array that causes any equal to run in the worst-case when n=5. (c) What is the best-case time complexity of any equal? (d) Draw an example of a two-dimensional array that causes any equal to run in the best-case when n=5. (e) Does any equal have an every-case time complexity? Why or why not? Consider the following algorithms. int add-them (int n, int A[]) { index i,j,k; j=0; for (i 1; in; i++) j=j+A: k=1; for (i=1;i; i++) k=k+k; return j+k; } int any equal (int n, int A[ ][ ]) { index i,j,k,m; for (i=1;in i++) for (j=1:j j++) for (k=1; kn; k++) for (m =1: mmm++) if (AA[k][m] && !(i == k &&j==m)) return 1; return 0; Note: The array parameter A[][] in any equal is an n x n two-dimensional array. For example, when n 5, then A is a 5 x 5 two-dimensional array. (a) Let's say that the basic operation of any equal is the evaluation of the if-statement, ie.. if (A[i][j]==A[k][m] && !(i==k&&j==m)) What is the worst-case time complexity of any equal when A is an n x n two-dimensional array? (b) Draw an example of a two-dimensional array that causes any equal to run in the worst-case when n=5. (c) What is the best-case time complexity of any equal? (d) Draw an example of a two-dimensional array that causes any equal to run in the best-case when n=5. (e) Does any equal have an every-case time complexity? Why or why not?