2. For each function f(n) and time t in the table below, find the largest size...

 

Transcribed Image Text:

2. For each function f(n) and time t in the table below, find the largest size n of a problem that can be solved in time t. Assume that the algorithm to solve the problem takes f(n) microseconds. For large entries, an estimate is acceptable. For one of the rows, you will not be able to solve it analytically, you may need to write a small program. Show your work. 1000 log n 100n 100n log2 n 10n2 n3 .2" 1 second 1 minute 1 hour 1 day 1 month 1 year 10 3. Prove or disprove: n log10 n (n log n). 2. For each function f(n) and time t in the table below, find the largest size n of a problem that can be solved in time t. Assume that the algorithm to solve the problem takes f(n) microseconds. For large entries, an estimate is acceptable. For one of the rows, you will not be able to solve it analytically, you may need to write a small program. Show your work. 1000 log n 100n 100n log2 n 10n2 n3 .2" 1 second 1 minute 1 hour 1 day 1 month 1 year 10 3. Prove or disprove: n log10 n (n log n).