StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POEmpirically estimating big-oh time efficiency
text
Body
copied!<h2>Background</h2> <p>I'd like to estimate the big-oh performance of some methods in a library through benchmarks. I don't need precision -- it suffices to show that something is O(1), O(logn), O(n), O(nlogn), O(n^2) or worse than that. Since big-oh means upper-bound, estimating O(logn) for something that is O(log logn) is not a problem.</p> <p>Right now, I'm thinking of finding the constant multiplier k that best fits data for each big-oh (but will top all results), and then choosing the big-oh with the best fit.</p> <h2>Questions</h2> <ol> <li>Are there better ways of doing it than what I'm thiking of? If so, what are they?</li> <li>Otherwise, can anyone point me to the algorithms to estimate k for best fitting, and comparing how well each curve fits the data?</li> </ol> <h2>Notes & Constraints</h2> <p>Given the comments so far, I need to make a few things clear:</p> <ul> <li>This needs to be automated. I can't "look" at data and make a judgment call.</li> <li>I'm going to benchmark the methods with multiple <code>n</code> sizes. For each size <code>n</code>, I'm going to use a proven benchmark framework that provides reliable statistical results.</li> <li>I actually know beforehand the big-oh of most of the methods that will be tested. My main intention is to provide performance regression testing for them.</li> <li>The code will be written in Scala, and any free Java library can be used.</li> </ul> <h2>Example</h2> <p>Here's one example of the kind of stuff I want to measure. I have a method with this signature:</p> <pre><code>def apply(n: Int): A </code></pre> <p>Given an <code>n</code>, it will return the nth element of a sequence. This method can have O(1), O(logn) or O(n) given the existing implementations, and small changes can get it to use a suboptimal implementation by mistake. Or, more easily, could get some other method that <em>depends</em> on it to use a suboptimal version of it.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload