CODEWITHSUNDEEP
asymptotic-complexitybig-o
Alyssa June
Alyssa June

Reputation: 725

Calculating Big Theta from Runtime?

I have a program that calculates the runtime in milliseconds of 4 .txt files. I then have to calculate what the runtime of the loading is in terms of theta, and specify what n refers to in the input. However I still do not exactly understand big theta notation or asymptotic notation at all, for that matter. Can anyone give me a few pointers? These were the runtimes for the files:

File Time to load

file1 18000ms

file2 48514ms

file3 121473ms

file4 622446ms

Upvotes: 0

Views: 210

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

There is no general way to derive a theta bound on the runtime of a program from its empirical runtime. There might be inputs you haven't seen that trigger pathological worst cases (for example, the simplex algorithm for linear programming degrades to exponential worst-case time on a narrow class of inputs) and you have no way of knowing whether the trends that you're seeing continue longer term.

If you want to derive the empirical computational complexity, a reasonable solution would be to take your data, plot it on a log/log axis, and look for a best-fit line. The reason this works is that a straight line on a log/log plot corresponds to a polynomial fit, so this will find the best fitting polynomial for the data you have. As long as you remember that your answer will only be as good as the data you provide, this is a great way to ballpark the complexity.

Upvotes: 1

Related Questions