1
$\begingroup$

Does anyone of you know how to associate an algorithm execution time (of experimental execution) to a well known complexity time? For example, say a divide and conquer algorithm lasts theoretically O(n·logn·n^2) or Ω(n·logn), in a theoretical way, doing reccurence ecuations and all that stuff. But when you plot the data from a CSV, you can't say just by looking at it 'oh yea this is O(n^2).

The data from the CSV is like:

n, execution_time_for_that_n...

How can I use a regression method to derive O-classes from such data?

$\endgroup$
3
$\begingroup$

It's impossible. No finite set of measurements can prove asymptotic bounds.

Proof sketch: Assume you had such a method. Apply it to any algorithm $A$. If your largest measurement is for input size $n_0$, construct a new algorithm $B$ that branches into $A$ for all $n \leq n_0$, and one with a different $\Theta$-runtime class for $n > n_0$. The method fails for $B$.

That said, there are ways to perform reasonable experiments (for average-case performance). I recommend the book "A Guide to Experimental Algorithmics" by C. McGeoch.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.