(25 pts) For each of the following code fragments: (a) Compute the worst-case ru
ID: 3750571 • Letter: #
Question
(25 pts) For each of the following code fragments: (a) Compute the worst-case run time as a function of n, i.e give the cxact expression for T(n). If there are any summations, simplify them. Show your work (i.e. next to each primitive statement write the total number of times it gets executed. You may assume that primitive statements have cost 1. Do not give just the final answers (b) Circle the higest order term and drop any multiplicative constants. What is the worst- case asymptotic time complerity T(n) of the algorithm?Explanation / Answer
for (i = 1; i <= N; i++) {
for (j = i+1; j <= N; j++) {
print i+j
}
}
Value of i Number of iterations of inner loop
0 N
1 N-1
2 N-2
... ...
N-2 2
N-1 1
So we can see that the total number of times the sequence of statements executes is: N + N-1 + N-2 + ... + 3 + 2 + 1. the statements in the inner loop execute a total of N * M times. Thus, the complexity is O(N * M). In a common special case where the stopping condition of the inner loop is j < N instead of j < M (i.e., the inner loop also executes N times), the total complexity for the two loops is O(N2).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.