N*Log(N) can be approximated to O(N) for most realistic usecases.

As for LLM, there is probably some cost constant added once it can fit on a single GPU, but should probably be almost linear.