a Suppose that a particular algorithm has time complexity Tn

Solution

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.