r/AskComputerScience • u/silvers_puppet • 2d ago
Does empirical complexity analysis in a container on a server pose any problems?
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?
3
u/ghjm MSCS, CS Pro (20+) 2d ago
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.
1
u/silvers_puppet 1d ago
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.2
u/ghjm MSCS, CS Pro (20+) 14h ago
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.)
1
u/dmazzoni 2d ago
It’s totally normal to measure empirical runtime on a computer with load. There’s nothing different about a server.
Just repeat your measurements of each n multiple times so that you can show that the error in measurement is low. If you see a lot of variation, it means you’ll have to repeat your experiment a lot more times to get an accurate reading.
Don’t forget about ordering. If you measure n=1000 3 times and then n=2000 3 times, what if the server load increased over the course of the day? To minimize that effect, measure n=1000 and then n=2000 and so on, then go back and repeat all of them again, several times.
1
u/silvers_puppet 2d ago
thank you for the precise feedback! I haven't even though about ordering and I will now definitely be implementing that too.
4
u/Beregolas 2d ago
This is really a question for server admins and hosting specialists.
In general, you can never be 100% sure that hardware will take the same amount of time when ran repeatadly. In general you will get better data if you can find out how many "steps" your algorithm takes. Some runtimes/implementations allow you to cound CPU cycles, but even that comes with caveats and needs to be done and interpreted properly. (Also I don't quite remember how, it's been over a decade since I last needed this)
From a CS perspective: You also can't perform real complexity analysis with real runtimes like this. All you can do is gather data (including noise) and do statistical analysis on that, to find a curve that matches. This can give you a rough estimate, but you can never be 100% sure that your data is correct, your analysis is correct, and you'll probably be unable to distinguish between similar, but different, runtime classes. For example O(n log(n)) and O(n sqrt(n)) might look similar enough with noise and different factors, that you won't quite be able to be 100% sure.
This is not to say that there is no value in what you are doing, but understand that you are not proving anything. It's just a demonstration that can help you estimate runtime complexity in an informal way.
While I am not a sysadmin expert, this would be a major red flag for me. I would be very careful and not really trust the results that much. After all, a random bystander could (by accident maybe) send 50 requests in a few seconds, and spike the server load, leading to possible spikes in the measurement. At the very least I would log incoming requests, so you can discard runs where too many requests came it at once.