Algorithms

Reading an exponent off a doubling experiment

Reading an exponent off a doubling experiment

You have run a program at a size, then at twice that size, then at twice that again, recording how many operations it performed each time. The measurements arrive in order, smallest input first, each input exactly double the one before.

If the cost behaves like c nbc\,n^b, then doubling the input multiplies the count by 2b2^b, so the exponent is the logarithm to base 2 of the ratio between two consecutive counts. Write growth_exponent(counts), which returns that exponent computed from the last two measurements, since those are the largest sizes and the least distorted by fixed start-up costs.

b  =  log⁡2 ⁣(last countthe count before it)b \;=\; \log_2\!\left(\frac{\text{last count}}{\text{the count before it}}\right)
Only the final pair is used, whatever the length of the list.

Worked example: with counts = [1000, 2000, 4000, 8000] the last two are 4000 and 8000, their ratio is 2, and the logarithm to base 2 of 2 is 1, so the answer is 1.0 and the growth is linear.

  • Constraints: the list has between 0 and 50 entries, and every entry is between 1 and 1000000000.
  • If there are fewer than two measurements there is no ratio to take, so return 0.0.
  • Answers are accepted within a small tolerance, so an ordinary floating point logarithm is fine.
  • The answer need not be a whole number. A cost of nlog⁡nn\log n gives an exponent slightly above 1, which is a correct reading rather than a mistake.
Code

Run your code to see how it does on the examples. Submit also runs the hidden cases.