Calculate running time using samples

Question

Suppose that you time a program as a function of N and produce the following table:

        N   seconds
-------------------
     4096      0.00
    16384      0.01
    65536      0.06    
   262144      0.51   
  1048576      4.41   
  4194304     38.10  
 16777216    329.13  
 67108864   2842.87

Estimate the order of growth of the running time as a function of N. Assume that the running time obeys a power law T(N) ~ a N^b.

Answer 1

Your N's are all consecutive powers of 4. Taking 4-based logarithm of consecutive ratios of times you'll see they converge to some constant which is known as 'b'. When you substitute N, T(N) and b from last entry of your table to power law (T(N) = a * N ^ b), you'll get 'a'. In your case log4 of times ratios converges to 1.555, so that's 'b'.

I guess you're taking Coursera's "Algorithms, Part I' course (as I do). Then, this thread must be available for you:

https://class.coursera.org/algs4partI-002/forum/thread?thread_id=149

Or, you may refer to "Analysis of Algorithms" slides beginning from page 16.

Answer 2

You need to to use a logarithmic graph (logN), and then take the slope of the line. That will indicate the exponent b.