Another big thing that doesn't get covered by big O analysis is the potential for parallelization and multi threading, because the difference created by multi threading only amounts to one of those dropped coefficients.

And yet, especially for the workloads being run on a server with 32-128 cores, being able to run algorithms in parallel will make a huge difference to performance.