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

No comments:

Post a Comment