a) Suppose that a particular algorithm has time complexity T(n) = 3 x 2^n, and t
ID: 3791018 • Letter: A
Question
a) Suppose that a particular algorithm has time complexity T(n) = 3 x 2^n, and that executing an implementation of it on a particular machine takes t seconds for n inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in t seconds?b) Suppose that another algorithm has time complexity T(n) = n^2, and that executing an implementation of it on a particular machine takes t seconds for n inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in t seconds?
c) A third algorithm has time complexity T(n) = 8n. Executing an implementation of it on a particular machine takes t seconds for n inputs. Given a new machine that is 64 times as fast, how many inputs could we process on the new machine in t seconds? a) Suppose that a particular algorithm has time complexity T(n) = 3 x 2^n, and that executing an implementation of it on a particular machine takes t seconds for n inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in t seconds?
b) Suppose that another algorithm has time complexity T(n) = n^2, and that executing an implementation of it on a particular machine takes t seconds for n inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in t seconds?
c) A third algorithm has time complexity T(n) = 8n. Executing an implementation of it on a particular machine takes t seconds for n inputs. Given a new machine that is 64 times as fast, how many inputs could we process on the new machine in t seconds?
b) Suppose that another algorithm has time complexity T(n) = n^2, and that executing an implementation of it on a particular machine takes t seconds for n inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in t seconds?
c) A third algorithm has time complexity T(n) = 8n. Executing an implementation of it on a particular machine takes t seconds for n inputs. Given a new machine that is 64 times as fast, how many inputs could we process on the new machine in t seconds?
Explanation / Answer
The key to working these problems is observing that the runtime T tells you roughly the
number of instructions executed. For example, suppose T = 1000 seconds and the old machine
will execute 106 instructions/second. Then in T seconds, the old machine will execute 106 ×103 = 109
instructions, and the new machine will execute 64 × 109 instructions. Thus, in
any given period of time the new machine will do 64 times as much work as the old machine.
Hence, if Told(n) is the runtime of a program on the old machine, its runtime will be
Tnew(n) = 1/64*Told(n)
A). We have Tnew(n) = 3 · 2n, and Told(n0) = T. We want to know for what value of n = n1
will we have Tnew(n1) = T. Using our formulas, we have
3 · 2n0 =1/64*3 · 2n1
.
So
64 · 2n0 = 2n1
,
and since 64 = 26
, we have
26+n0 = 2n1
.
Thus, n1 = 6 + n0. If, for example, we could previously solve a problem of size 100, we
can now solve a problem of size 106.
B). Using reasoning similar to that in part (a),
we have n02 = 1/64 *n12 . So n02 =n12 , and 8n0 = n1. So we can
solve a problem 8 times larger on the new machine.
C). ) Reasoning as in part (a) again, we have 8n0 = 1/64 *8n1, and 64n0 = n1.
So we can solve a problem 64 times larger on the new machine.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.