4
$\begingroup$

Is it in general acceptable by computer science community, if the run-time or space consumption of an algorithm is derived by experiment and not analytically?

For example let's say we have an algorithm for which it's running time is given by function $f(n)$, where $n$ is the size of the problem. There is no way to derive its asymptotic behaviour (respecting run time) analytically but only using numerical methods. In other words we have no analytical expression for $f(n)$ but we can probe it using specific values for $n$. Making some trials (trying a wide range of n) we see that run time follows for example very closely a line. Let's say that doing least square method we observe that $t= an+b$ is a good fit for the run time t of the problem (of size n). Good fit is a vague term, and I mean that residuals are within acceptable ranges.

So is it safe to say that the run time of this algorithm is $\Theta(n)$, at least in the range we made the trials? Moreover can we state that this algorithm is faster than another one whose asymptotic behavior is for example $O(n^2)$.

If the answer is negative, what other methods should I search for?

$\endgroup$
  • 1
    $\begingroup$ Note that the phrase "analytic function" has a well-defined meaning, which probably isn't the one that you intended. $\endgroup$ – David Richerby Mar 16 '17 at 11:32
  • $\begingroup$ David Richerby you are right, with the word analytic I mean that $f(n)$ has not analytic expression, I will edit the question accordingly, thanks for the comment $\endgroup$ – Curious_Dim Mar 16 '17 at 16:13
3
$\begingroup$

Is it safe? No, of course, it's not safe. There could always be ways that your experiments are misleading. Maybe the worst case wasn't triggered by your particular workload or in your particular experiments. Maybe there's a quadratic term with a small constant, which is negligible for the values of $n$ you tested in your experiments but becomes dominant for very large values of $n$. You can't rule out those possibilities with experiments.

Are the experiments good enough? That depends on the community, and for what purpose you want to use them, and what conclusions you want to support. Can you conclude that the worst-case running time, over all possible inputs, is linear? No. Can you conclude that for workloads that are likely to arise in practice, the running time appears to be linear? Perhaps. Is this enough to conclude that your system or your method has merit or is a significant contribution over the state of the art? Quite possibly.

There is no single answer about what is "acceptable". Instead, I suggest you take a broader, more nuanced view. Understand the strengths and limits of any method of analysis; understand what conclusions you can and can't support, using those methods; understand what claims you want to be able to make; understand the values of your audience nad the community you are targetting; and go from there.

$\endgroup$
1
$\begingroup$

It depends on which part of the computer science community your are aiming for as audience; the computer science community is not monolithic. Theoretical computer science is about provable facts, and won't care about your experiments. Other parts could be more accepting toward empirical results.

$\endgroup$
  • $\begingroup$ How about data base community? The problem is that maybe there is no other way to prove the linearity of that algorithm, and successful linear fitting for specific values is just an indication that the linearity is true. I have to notice that by saying experiments I don't mean the case that we just measure the running time using a stopwatch, but we compute it numerically. $\endgroup$ – Curious_Dim Mar 15 '17 at 19:20
  • $\begingroup$ Unfortunately I don't belong to the database community. Perhaps somebody from that community will answer. $\endgroup$ – Yuval Filmus Mar 15 '17 at 19:22
  • $\begingroup$ So I suppose from you perspective it's not enough. Maybe if I bound $f(n)$ from above and below with linear analytic functions will give me these provable facts $\endgroup$ – Curious_Dim Mar 15 '17 at 19:29

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.