Suppose that a particular algorithm has time complexity T(n) = 3 \times 2^n 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?

n+6

  • 6
  • 3
  • 3n
  • 6n
  • n^2
  • n+3
  • 64
  • 64n

This problem has an exponential growth rate. The behavior of an exponential growth rate is different from a polynomial growth rate.

With a polynomial growth rate, a faster computer leads to a new problem size that is bigger by some factor multiplied by the original problem size that can done in the same amount of time.

But with an exponential growth rate, we only get an additive improvement.

Regardless of the value of t, the machine that is 64 times faster can only do a problem size that is 6 larger in the same amount of time (because \log 64 = 6).