Suppose that a particular 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?

8n

  • 8
  • 2^n
  • n^2
  • 8n^2
  • 64
  • 64n
  • 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 n^2 = 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) = n^2?

If n^2 \approx S, then T(8P) = (8P)^2 \approx 64S.