Q3. (5 points) Give the complexity (in e notation) of each of the following with justification....

   

Transcribed Image Text:

Q3. (5 points) Give the complexity (in e notation) of each of the following with justification. (a) for (i=0; i < log(n); i++) for (j=0; j < 10; j++) sum++; Complexity: ................) Justification: (b) for (i 1; i < n*n; 1-2*1) sum++; Complexity: ...............) Justification: - (c) for (i=0; i < n; i++) for (i Sum++; < n; j++) Complexity: ...............) Justification: (d) for (i=0; i < n; i++) for (1; j < n; j = 2*j) sum++; Complexity: ...............) Justification: (e) for (i = n; i >= 1; 1 = 1/2) for (j=0; j < 1; j = j++) Sum++; Complexity: ...............) Justification: || Q3. (5 points) Give the complexity (in e notation) of each of the following with justification. (a) for (i=0; i < log(n); i++) for (j=0; j < 10; j++) sum++; Complexity: ................) Justification: (b) for (i 1; i < n*n; 1-2*1) sum++; Complexity: ...............) Justification: - (c) for (i=0; i < n; i++) for (i Sum++; < n; j++) Complexity: ...............) Justification: (d) for (i=0; i < n; i++) for (1; j < n; j = 2*j) sum++; Complexity: ...............) Justification: (e) for (i = n; i >= 1; 1 = 1/2) for (j=0; j < 1; j = j++) Sum++; Complexity: ...............) Justification: ||