Hardware vendor XYZ Corp. claims that their latest computer will run 100 times faster than that of their competitor, Prunes, Inc. If the Prunes, Inc. computer can execute a program on input of size n in one hour, what size input can XYZ's computer execute in one hour for an algorithm whose growth rate is n^2?

10n

  • 10
  • 100
  • 100n
  • n
  • n^2
  • 10n^2
  • 100n^2
  • n+10
  • n+100

If the XYZ Corp. computer runs 100 times faster, then if the Prunes computer does S computations in an hour, the XYZ Corp. computer does 100S computations in an hour.

Assume that the Prunes computer can solve a problem size of at most P in an hour. This means it makes about P^2 = S computations.

How much bigger size than P can run in 100S, given that the growth rate of the algorithm on input size P is T(P) = P^2?

If P \approx S, then T(10P) = (10P)^2 \approx 100S.