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

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
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
