1. Algorithms X and Y take exactly T.(n) = cinlogn and Ty(n) = cn microseconds, respectively,...

 

Transcribed Image Text:

1. Algorithms X and Y take exactly T.(n) = cinlogn and Ty(n) = c₂n³ microseconds, respectively, for a problem of size n. Find the best algorithm for processing n = 220 data items if the algorithm X takes 10 microseconds to process 1024 items and the algorithm Y takes only 1 microsecond to process 1024 items? 2. If f(n) = n²/log n and g(n) = n(log n)², Explain (using algebraic expression) whether f(n) is in O(g(n)), 2(g(n), or 0(g(n)) ? 3. For the given code segment sum = 0; for(i=0;i<sqrt(n)/2;i++) sum++; for(j=0;j<sqrt(n)/4;j++) sum++; for(k 0;k<8+j;k++) sum++; (a) If it takes 0.5 ms for input size 100. How long will it take for input size 500 with respect to its running time (Big-Oh notation)? 4. Give an analysis of the running time (Big-Oh notation) for the following program fragments. Note that the running time corresponds here to the number of times each step is executed? (a) for(i=1;i<2*n;i++) for(j=1:j<i*i;j++) for(k=1;k<j;k++) if (j %i) sum++; (b) int count = 0; for (int i=n/2; i<n; i++) } for (int j=1; j<n; j = 2 *j) (c) int i=1, s=1; while (s <= n) { (d) i=n; for (int k=1; k<n; k = k * 2) count++; i++; s += i; while(i > 1) { while (j<n) { } i=i/2; k = 0; while (k <n) { } j<--j*2; k=k+ 2; } (e) Order the computed time complexities (a - d) by growth rate from slowest to fastest 1. Algorithms X and Y take exactly T.(n) = cinlogn and Ty(n) = c₂n³ microseconds, respectively, for a problem of size n. Find the best algorithm for processing n = 220 data items if the algorithm X takes 10 microseconds to process 1024 items and the algorithm Y takes only 1 microsecond to process 1024 items? 2. If f(n) = n²/log n and g(n) = n(log n)², Explain (using algebraic expression) whether f(n) is in O(g(n)), 2(g(n), or 0(g(n)) ? 3. For the given code segment sum = 0; for(i=0;i<sqrt(n)/2;i++) sum++; for(j=0;j<sqrt(n)/4;j++) sum++; for(k 0;k<8+j;k++) sum++; (a) If it takes 0.5 ms for input size 100. How long will it take for input size 500 with respect to its running time (Big-Oh notation)? 4. Give an analysis of the running time (Big-Oh notation) for the following program fragments. Note that the running time corresponds here to the number of times each step is executed? (a) for(i=1;i<2*n;i++) for(j=1:j<i*i;j++) for(k=1;k<j;k++) if (j %i) sum++; (b) int count = 0; for (int i=n/2; i<n; i++) } for (int j=1; j<n; j = 2 *j) (c) int i=1, s=1; while (s <= n) { (d) i=n; for (int k=1; k<n; k = k * 2) count++; i++; s += i; while(i > 1) { while (j<n) { } i=i/2; k = 0; while (k <n) { } j<--j*2; k=k+ 2; } (e) Order the computed time complexities (a - d) by growth rate from slowest to fastest

Answer rating: 100% (QA)

1 It is given that Tx C n log n microseconds We hav... View the full answer