What is the asymptotic running time of the following algorithm to compute the su
ID: 3759369 • Letter: W
Question
What is the asymptotic running time of the following algorithm to compute the subsequence sum problem?
maxSum := 0
For i = 1 to n
For j = i to n
Sum := 0
For k = i to j
End-for
If ( Sum > maxSum ), then maxSum := Sum
End-for
End-for
Here is a more efficient algorithm for solving the maximum subsequence sum problem. What is the asymptotic running time of this algorithm?
maxSum := 0
For i = 1 to n
Sum := 0
For j = i to n
If ( Sum > maxSum ), then maxSum := Sum
End-for
End-for
maxSum := 0
For i = 1 to n
For j = i to n
Sum := 0
For k = i to j
Sum := Sum +
End-for
If ( Sum > maxSum ), then maxSum := Sum
End-for
End-for
Explanation / Answer
maxSum := 0
For i = 1 to n //Run for n times
For j = i to n //Run for n times
Sum := 0
For k = i to j //This will run for 1+2+3+4....n = n*(n+1)/2
Sum := Sum + a_k
End-for
If ( Sum > maxSum ), then maxSum := Sum
End-for
End-for
//hence the complexity for above algorithm is O(n^3)
maxSum := 0
For i = 1 to n //Run for n times
Sum := 0
For j = i to n //Run for n times
Sum := Sum + a_j
If ( Sum > maxSum ), then maxSum := Sum
End-for
End-for
//hence the complexity for above algorithm is O(n^2)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.