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?

Answer 1

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*T_old(n)
  
A). We have T_new(n) = 3 · 2ⁿ, and T_old(n0) = T. We want to know for what value of n = n1
will we have T_new(n1) = T. Using our formulas, we have
3 · 2ⁿ⁰ =1/64*3 · 2ⁿ¹
.
So
64 · 2ⁿ⁰ = 2ⁿ¹
,
and since 64 = 2⁶
, we have
2⁶⁺ⁿ⁰ = 2ⁿ¹
.
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 n₀² = 1/64 *n₁² . So n₀² =n₁² , and 8n₀ = n₁. So we can

solve a problem 8 times larger on the new machine.

C). ) Reasoning as in part (a) again, we have 8n₀ = 1/64 *8n₁, and 64n₀ = n₁.

So we can solve a problem 64 times larger on the new machine.