3 ms·
You're failing to account for the fact that it's a log-log graph, though, so even a modest slope can be pretty significant. If you want a rule of thumb, might
by stdbrouw 10y ago
You're failing to account for the fact that it's a log-log graph, though, so even a modest slope can be pretty significant.
If you want a rule of thumb, might as well just stick to "hash tables are fast" instead of the false precision of O-notation.
- jimminy 10y agoBig O-notation isn't precise, it is an approximation by nature. It only cares about the largest factors for determining the estimate.
- epistasis 10y agoThe log-log graph is the way to determine those large factors. Taking the log removes the multiplicative constants. The differences between n^.5 and n^1 and n^1.5 are quite significant for big-o
- aaronbwebber 10y agoThe graph really is totally flat below the L1 cache size line, and even on a log-log graph the slope between 10 MB and 1 GB is not significant.
- AstralStorm 10y agoThat being kB range for L1, single digit MB for L2. Relatively simple Java apps tend to eat multiple GB, while accessing most of it.