Suppose that a particular algorithm has time complexity T(n) = 8n 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?

64n

  • 8
  • 2^n
  • n^2
  • 8n^2
  • 64
  • 8n
  • 64n^2

If the slower computer does S computations in time t, then the faster computer does 64S computations in time t.

Assume that the slower computer can solve a problem size of at most n in time t. This means it makes about 8n = S computations.

How much bigger size than n can run in 64S, given that the growth rate of the algorithm on input size n is T(n) = 8n?

If 8n \approx S, then T(64n) = 64*8n \approx 64S.