StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The first response covers how to prove the time complexity of your algorithm quite well.</p> <p>However, you seem to be asking how to relate the experimental results of your benchmarks with time complexity, <em>not</em> how to prove time complexity.</p> <p>So, how do we interpret the experimental data? Well, you could start by simply plotting the data (runtime on the y-axis, size on the x-axis). With enough data points, this could give you some hints about the behavior of your algorithm.</p> <p>Since you already know the expected time complexity of your algorithm, you could then draw a "curve of best fit" (i.e. a line of the shape n^3 that best fits your data). If your data matches the line fairly well, then you were likely correct. If not, it's possible you made some mistake, or that your experimental results are not matching due to factors you are not accounting for.</p> <p>To determine the equation for the best fitting n^3 line, you could simply take the calculated time complexity, express it as an equation, and guess values for the unknowns until you find an equation that fits. So for n^3, you'd have:</p> <pre><code>t = a*n^3 + b*n^2 + c*n + d </code></pre> <p>Find the values of a, b, c, and d that form an equation that best fits your data. If that fit still isn't good enough, then you have a problem.</p> <p>For more rigorous techniques, you'd have to ask someone more well versed in statistics. I believe the value you'd want to calculate is the <a href="http://en.wikipedia.org/wiki/Coefficient_of_determination" rel="nofollow">coefficient of determination</a> (a.k.a. R^2, basically tells you the variance between the expected and actual results). However, on it's own this value doesn't prove a whole lot. This problem of validating hypothesized relationships between variables is known as <a href="http://en.wikipedia.org/wiki/Regression_model_validation" rel="nofollow">Regression Model Validation</a>; the wikipedia article provides a bit more information on how to go further with this if R^2 isn't enough for your purposes.</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