For each function f(n) and time t in the following table, determine the largest

Question

For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds (1 second equals 1 million microseconds). For large entries (say, those that warrant scientific notation), an estimate is sufficient. Note that for one of the rows, you will not be able to solve it analytically, and will need a calculator, spreadsheet, or small program. This problem gives an orthogonal view of comparative running times from that given in lecture. Be sure to look at the patterns in your table when you have completed it.

Explanation / Answer

500 log2n->22000 in a second and multiply 60,3600,86400,2592000 and 31536000 to 22000 for min,hour,day,month and year.

1000n -> 1000 in a second and multiply like above

100n log2n -> 100 in a second and...........

10n2 -> 316.23 =316 in a second

2 n3 ->79.37 in a seond = 79

1/20 2n -> 24.25 =24

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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