# Asymptotic behavior of functions with not analytic expression

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?

• Note that the phrase "analytic function" has a well-defined meaning, which probably isn't the one that you intended. – David Richerby Mar 16 '17 at 11:32
• 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 – Curious_Dim Mar 16 '17 at 16:13

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.
• 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 – Curious_Dim Mar 15 '17 at 19:29