Monday, October 28, 2013
How to calculate order of growth of function
I am taking the Algorithm course on coursera and in the exercise there are questions around calculating order of growth of function like this
Suppose that you time a program as a function of N and produce the following table.
N seconds
-------------------
36 0.00
216 0.05
1296 16.67
7776 5933.65
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.
Initially it was difficult for me to figure out how to calculate the order of growth or where to start. But then i found this nice discussion which explains the procedure for calculation
N Order of growth of N Seconds Order of growth of time
36 0.00
216 6 0.05
1296 6 16.67 333.4
7776 6 5933.65 355.947
Now the average value of order of growth of time is 344.6735. Value of growth of N is 6.
So the last step would be calculate log base of (Order growth of N) (Order of growth of time). In my case it would be log_6(344.6735) which comes out to 3.26. I used online log calculator
Subscribe to:
Posts (Atom)