Give a big-O estimate for the number of additions used in the following algorith

Question

Give a big-O estimate for the number of additions used in the following algorithm segment. t := 0; for i : = l to n for j= l to i t := t + i + j Assume each basic operation takes 10 - 8 sections. If an algorithm A takes f(n ) = 2 . n2 operations and n = 20000, how many seconds does it take? If an algorithm B takes g(n) = n 4/5 operations, and we have 1 hour computing time, how large (n =?) a problem can we solve? Estimate the growth rate of the following functions in big-O notation. f1(n) = 4n4 - 16n2 + 7 f2(n) = (n2 + n log n) . (n3 - 6n log n)

Explanation / Answer

12. the second loop iterates for 1, 2, 3... m-1 times, so altogether: 1 + 2 +...+ m-1 = n(n-1)/2 which is O(n^2) 13. 2n^2 = 2 * (2*10^5)^2 = 8 * 10^10 operations * 10^-8 sec = 800 seconds (n^4)/5 instr * 10^-8 = 3600sec (you can solve this for n I imagine :) 14. in Big Oh we are only interested in a dominating term so it is 1. O(n^4) 2. O(n^5) rate pls :)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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