2. For each of the following three program fragments, give an analysis of the running time....

Transcribed Image Text:

2. For each of the following three program fragments, give an analysis of the running time. First, give the total number of times of each statement being executed. Then give the summed/total time in Big- O notation using function with the least order of magnitude. Basically don't say the complexity is O(N9) if it is also O(N2). (21 pts) (a) Sum = 0; for(i= 1; i N; i++) Sum Sum + i; (b) Sum= 0; for(i=1;i< N;i++) for(j= 1; j≤ N²; j++) for(k = 1; k< N; k++) Sum Sum + 1; (c) Sum = 0; for (i = 1; i ≤ N; i++) for(j= 1; ji; j++) Sum Sum + 1; (d) x = 100; y = 0; for(i= 1; i ≤ N; i = 2 * i) x = x + i; for(j= 1; j< N; j++) if(x > y/j) y = y + i/j; else y = y - 1; 2 2. For each of the following three program fragments, give an analysis of the running time. First, give the total number of times of each statement being executed. Then give the summed/total time in Big- O notation using function with the least order of magnitude. Basically don't say the complexity is O(N9) if it is also O(N2). (21 pts) (a) Sum = 0; for(i= 1; i N; i++) Sum Sum + i; (b) Sum= 0; for(i=1;i< N;i++) for(j= 1; j≤ N²; j++) for(k = 1; k< N; k++) Sum Sum + 1; (c) Sum = 0; for (i = 1; i ≤ N; i++) for(j= 1; ji; j++) Sum Sum + 1; (d) x = 100; y = 0; for(i= 1; i ≤ N; i = 2 * i) x = x + i; for(j= 1; j< N; j++) if(x > y/j) y = y + i/j; else y = y - 1; 2

Answer rating: 100% (QA)

Answer A Lets analyze the running time for each of the given program fragments Sum 0 fori 1 i N i Su... View the full answer