Do it Your Self. Do not copy and paste exist answer, there is a exactly same que

Question

Do it Your Self. Do not copy and paste exist answer, there is a exactly same question posted before and the answer is incorrect.

Thank you very very much.

(1. 6pts) Computational problem solving: Estimating problem solving time Suppose that there are three algorithms to solve a problem: a O(n) algorithm (A1), a O(nlogn) algorithm (A2), and a 0(n2) algorithm (A3), where log is to the base 2. Using the techniques and assumptions presented in slide set L2-Buffet(SelectionProblem), determine how long in seconds it will take for each algorithm to solve a problem of size 200 million. You must show your work to get credit, i.e., a correct answer without showing how it is derived will receive zero

Explanation / Answer

By the techniques and assumptions presented in slide set L2-Buffet (Selection Problem),

there is a computer running at 4 x 109 clock cycles per second. This machine typically requires about 200 clock cycles to execute one computation step.

So, the computer will execute ( 4x 109)/(200) = 2 x 107 ops per second.

Hence,

A1 O(n) will take : (200 x 106) / (  2 x 107 ) = 10 seconds

A2 O(n log(n) ) will take = [  2 x 108 x log2(  2 x 108 ) ] / [ 2 x 107 ] = 275.75 seconds

A3 O(n2) will take = [  2 x 108 ]2 / [  2 x 107 ] = 2 x 1016-7 = 2 x 109 seconds = 64.300411 years ( approx.)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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