3. What is the Big-O running time of the following pseudocode? a) // a, b, c...

Transcribed Image Text:

3. What is the Big-O running time of the following pseudocode? a) // a, b, c are 2D arrays of int int i, j, k; for (i=0; i<N; i++) { for (j=0; j<N; j++) { c[i][j] = 0; for (k=0; k<N; k++) c[i]c[j] = += a[i][k] * b[k][j]; } b) //X is a 2D array of ints // Each row in x is sorted // search returns the value, or -1 if not found // each search runs in the O(log N) time int count = 0; for (int i=0; i<X.length; i++) { // search for the value in row i of X int result = search(X[i], value); if (result == value) count++; } c) //X is a sorted array of N ints // X is large enough to hold 10 extra values for (int i=0; i<10; i++) { // get a value in constant time int value = getValue(); // insert the value in the list in soreted order int result insert(X, value); } 3. What is the Big-O running time of the following pseudocode? a) // a, b, c are 2D arrays of int int i, j, k; for (i=0; i<N; i++) { for (j=0; j<N; j++) { c[i][j] = 0; for (k=0; k<N; k++) c[i]c[j] = += a[i][k] * b[k][j]; } b) //X is a 2D array of ints // Each row in x is sorted // search returns the value, or -1 if not found // each search runs in the O(log N) time int count = 0; for (int i=0; i<X.length; i++) { // search for the value in row i of X int result = search(X[i], value); if (result == value) count++; } c) //X is a sorted array of N ints // X is large enough to hold 10 extra values for (int i=0; i<10; i++) { // get a value in constant time int value = getValue(); // insert the value in the list in soreted order int result insert(X, value); }

Answer rating: 100% (QA)

1 a b c are 2D arrays of int int i j k for i0 i for j0 j cij 0 for k0 k cij aik bkj Therefore ... View the full answer