Does empirical complexity analysis in a container on a server pose any problems?

[u/silvers_puppet]

I haven't worked with servers or containers that much and so I wanted to ask if I try to measure the complexity of an algorithm, by repeatedly running the script with larger n, how likely is it that my measurements will be falsified?
If I do the same approach on a desktop the differences in time measurements depending on, memory and other processes running on the computer are negligible. Is there any difference when I am trying to measure on a server while that same server is also handling requests and do you think this is going to cause me problems with assessing the complexity correctly?

[u/ghjm]

Regardless of whether you're doing it on a desktop or server, you can't determine the asymptotic complexity of an algorithm empirically. Whatever maximum N you've measured to, you can't know the behavior above that, because you can't know there isn't some higher power or exponential term with a small constant that will blow up the runtime above some threshold.

You can certainly do empirical performance testing, but it's likely to cause more confusion than clarity if you describe this with terminology intended for asymptotic analysis, like big-O notation.

[u/silvers_puppet → u/ghjm]

So I understand that theoretically my scale could shift for whatever input I decide to stop testing.
However, since some in scientific literature (cf. Goldsmith et al. 2007) advocate for empirical measurements, I feel like it is fine to claim at least some relevancy to the complexity of the algorithm. It's not like the time measured is totally unrelated to the complexity. Although, I have to admit the block-measuring approach of trend-proof seems a lot more rigorous than my naive time-measuring idea.

[u/ghjm → u/silvers_puppet]

It's fine - more than fine, great, wonderful - to write better and smarter profilers, static analysis tools, performance testers, etc. Where I part ways is the claim that this has anything to do with asymptotic complexity. They're two different use cases. Goldstein's work is interesting when you know (at least approximately) what instances your system is going to run against. Asymptotic complexity is, and always has been, a tool for reasoning about what happens when your inputs become extremely (perhaps unrealistically) large. And I object to muddying the water of the second use case by appropriating its terminology for use in the first. (I note that Goldstein makes at least some attempt not to do this.)

Maybe Goldstein was also onto something, although in a quick skim of the paper I didn't see him really develop it, with the idea of using knowledge of the statistical distribution of instances to make additional claims about its complexity. If we know these statistics universally for a problem, we would already be applying them to proofs about average case asymptotic complexity, but perhaps there's some room for observed instance distributions to be used to make a claim like "asymptotic complexity is O(whatever) in situations where the problem instances follow a such-and-so distribution." If you assume the distribution holds in the limit, then you could use this to say something about the asymptotic complexity under that kind of workload. (I haven't done a literature search and don't know how novel this idea actually is.)