6. Following two algorithms are presented as solutions for a problem Which algor

Question

6. Following two algorithms are presented as solutions for a problem Which algorithm is more efficient and why? You should address the efficiency in terms of complexity (Big-Oh) of the two algorithms. You may use examples to explain. (10 points) Eample array: int[] array { Algorithm 1 best sum 0 for (i-0 through N) for G-i through N) current sum=0 for (k-i through j) current sumarray[k] if (current sum > best sum) best sum current sum Algorithm 2 best sum 0 for (i 0 to N) current _sum 0 for (j-i to N) current_sumarray[k] if (current sum> best sum) best sumcurrent sum

Explanation / Answer

(Ans-)Algorithm 2 is more efficient than Algorithm 1. Since in Algorithm 2, there are only 2 for loops, But in Algorithm 1, there are 3 for loops. Because of this, The running time complexity in Algorithm 1 is O(N^3) and the running time complexity in Algorithm 2 is O(N^2). Algorithm 2 will take less time than Algorithm 1 and do the same than Algorithm 1.

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.