(10 pts) For each of the following program fragments compute the worst-case asym
ID: 3888746 • Letter: #
Question
(10 pts) For each of the following program fragments compute the worst-case asymptotic time complexity (as a function of n). Whenever it says ”loop body” you can assume that the constant number of statements are executed inside the body. Briefly explain how you obtained your answer (show your work by writing on the side of the pseudo-code the number of times the corresponding statements get executed. (Use summations when needed to express the number of times each of the loop bodies is executed.)
(a) for (i=1; 0 <= n-1; i++){ loop body
}
for (i=0; i <= n-2; i++){
for (j=i+1; j<= min(i+10, n-1); j++){ loop body
}
}
(b) for (i=0; i <= n-1; i++){ loop body
}
for (i=0; i <= n-1; i++){
for (j=i+1; j <= n-1; j++){ for (k = 0; k <= n-1; k++){
loop body
}
}
}
I'm entirely new to Data Structures and Algorithms, so I could sure use some help on approaching this problem, and even a step-by-step solution.
Explanation / Answer
Hey in the comments i have written which loop gets executed how many times and below every part is the worst case complexity.If you have any doubts feel free to comment
(a) for (i=0; i <= n-1; i++){ loop body
//this get executed n times
}
for (i=0; i <= n-2; i++){
//this gets executed n-1 times
for (j=i+1; j<= min(i+10, n-1); j++){ loop body
// in the worst case this gets executed n*(n+1)/2 times if n<9
}
}
So worst case complexity for part a is 0(n^2)
(b) for (i=0; i <= n-1; i++){ loop body
//this gets executed n times
}
for (i=0; i <= n-1; i++){
//this get executed n times
for (j=i+1; j <= n-1; j++){
//this get executed n*(n+1)/2 times
for (k = 0; k <= n-1; k++){
//this gets executed n*n*(n+1)/2 times
loop body
}
}
}
so the worst case complexity for part b is 0(n^3)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.