it's implicitly O(n log n) because you need to do O(log n) for an interesting operation on each request.
Still, that means doubling your traffic adds a fixed amount of computation due to the log n component. That doesn't turn 16x into 64x. It turns 16x into 16x+y, where if you 16x again it turns into 256x+2y.