Add a row to Table 1.1 showing the approximate maximum input size that can be so

Question

Add a row to Table 1.1 showing the approximate maximum input size that can be
solved in one day, for each column  

Algorithm 4 46nlgn 13n2 3.4 2" Time function (microsec.)33n Input size (n) Solution time 10 .00033 sec. .0015 sec. .0013 sec. .0034 sec 001 sec 3.4 sec. 4 1016 yr 94 hr 100 .003 sec 1,000.033 sec 10,000 .33 sec 03 sec 45 sec 6.1 sec 13 sec 13 sec 22 min. 1.3 min. .5 days 108 yr 39 days 00,000 3.3 sec Time allowed Maximum solvable input size (approx.) 2,000 82,000 1 second 30,000 280 67 20 1 minute1,800,000 2,200 260 26 Table 1.1 How functions grovw

Explanation / Answer

1 day = 24 hours = 24 * 60 minutes = 24 * 60 * 60 seconds = 24 * 60 * 60 * 10^6 microseconds = 86400000000 microseconds = 8.64 * 10^(10) micro seconds

For the first case, largest n will be

33n = 8.64 * 10^(10)

n = 2.618 * 10^9

For the second case.

46nlog(n) = 8.64 * 10^(10)

nlog(n) = 1.8782 * 10^9

n = 1.018 * 10^8

For the third case,

13n^2 = 8.64 * 10^(10)

n^2 = 6.64 * 10^9

n = (66.4 * 10^8)^(0.5) = 8.1523 * 10^4

For the fourth case

3.4n^3 = 8.64 * 10^(10)

n^3 = 25.4 * 10^9

n = 1364.61

For the last case

2^n = 8.64 * 10^(10)

n = log(8.64 * 10^(10)) = 36.33

Hence largest input will be 36

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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