Question

• Suppose that a particular algorithm has time complexity T(n) = 10 ∗ 2n, and that execution of the algorithm on a particular machine takes T seconds for n inputs. Now, suppose you are presented with a machine that is 64 times as fast as your current machine. How many inputs can you process on you new machine in T seconds?

Answer 1

Answer:

The number of inputs processed by the new machine is 64

Solution:

As per the question:

The time complexity is given by:

$T(n) = 10\times 2n$

where

n = number of inputs

T = Time taken by the machine for 'n' inputs

Also

The new machine is 65 times faster than the one currently in use.

Let us assume that the new machine takes the same time to solve k operations.

Then

T(k) = 64 T(n)

$\frac{T(k)}{T(n)} = 64$

$\frac{20k}{20n} = 64$

k = 64n

Thus the new machine will process 64 inputs in the time duration T