3. Suppose that algorithm A (for some problem) takes 2n/2 basic computer steps f

Question

3. Suppose that algorithm A (for some problem) takes 2n/2 basic computer steps for an input of size n. (a) Suppose you run algorithm A on a computer whose processor can complete 109 basic computer steps in 1 second. What is the largest input size for which A can solve the problem in 1 hour of processor time? (b) You anticipate that next year you will be able to buy a new computer whose processor is 10 times faster. If you used this new computer next year, what is the largest input c) Suppose that you thought about your problem carefully and were able to come up with a new algorithm B that solved the problem using n2 basic computer steps. What is the largest input size for which B can solve the problem in 1 hour of processor time on your current computer?

Explanation / Answer

a) basic steps done in 1 sec = 109

basic steps done in 3600 sec(1 hour) = 3600 * 109

2n/2 basic steps are done for input size n

Here number of basic steps = 3600 * 109

thus,

2n/2 = 3600 *109

=> log 2n/2 = log 3600 * 109

=> (n log 2)/2 = 12.556

=>n = 12.556*2/log2 = 82.4285 = 82(rounding down)

Thus A would solve a max input size of 82 in 1 hour

b) New processor is 10 times faster. So it would solve 10*109 = 1010 basic steps in 1 sec and hence 3600 * 1010 basic steps in 3600 sec( 1 hour ).

Thus ,

2n/2 = 3600 * 1010

=> n/2 = (log(3600 * 1010))/log2 = 45.033

=> n = 45.033*2 = 90.066 = 90(rounding down

Thus new processor would solve a max input size of 90 in 1 hour

c) For the current processor , 109 basic steps are done in 1 sec.

Now, There are algorithm B has n2 basic steps for inout size n.

In one hour the computer can compute 3600 * 109 basic steps.

Thus,

n2 = 3600 * 109

=> n = 1897366.5961 = 1897366

Thus max input size = 1897366

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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