CODEWITHSUNDEEP
algorithmbig-ocomplexity-theory
Mohamed Naguib
Mohamed Naguib

Reputation: 1730

Calculate running time using samples

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.

Upvotes: 3

Views: 4009

Answers (5)

freedev
freedev

Reputation: 30137

For me it is more clear in this way:

N           seconds     log(N, 2)   log(seconds, 2)  Y(n)-Y(n+1)/
                            or X     or Y            X(n)-X(n+1)
----------------------------------------------------------------------------
4096              0         12      #NUM!
16384          0.01         14      -6.64385619         1.29248125
65536          0.06         16      -4.058893689        1.543731421
262144         0.51         18      -0.9714308478       1.556104752
1048576        4.41         20      2.140778656         1.555470218
4194304        38.1         22      5.251719093         1.555397315
16777216     329.13         24      8.362513723         1.555309345 
67108864    2842.87         26      11.47313241

The answer: b is roughly 1.55

Estimate the order of growth of the running time as a function of N. This is the google drive version...

Upvotes: 0

Rail Suleymanov
Rail Suleymanov

Reputation: 359

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.

Upvotes: 4

argentage
argentage

Reputation: 2778

Use the least-squares fitting power law:

http://mathworld.wolfram.com/LeastSquaresFittingPowerLaw.html

This will give you the closest fit for a and b which you can then use to extrapolate the runtime of new points.

Upvotes: 0

noMAD
noMAD

Reputation: 7844

You can calculate the slope between every two samples for the entire sample set. You can then do this recursively (slope of slopes). That should give you b

Upvotes: 0

Srikant Krishna
Srikant Krishna

Reputation: 881

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

Upvotes: 2

Related Questions