3 ms·
How does it follow that with O(log n) complexity you get 64x more work with 16x more data?
by mruts 8y ago
How does it follow that with O(log n) complexity you get 64x more work with 16x more data?
- naniwaduni 8y agoit's implicitly O(n log n) because you need to do O(log n) for an interesting operation on each request.
- hexane360 8y agoStill, 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. Logs grow slowly.