Asymptotic behavior of functions with not analytic expression

Question

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?

Answer 1

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.

Answer 2

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.