4 ms·
If I understood it correctly, the author links cache miss from memory subsystem hierarchy to asymptotic complexity (big O), so if an operation for fixing a cach
by faragon 10y ago
If I understood it correctly, the author links cache miss from memory subsystem hierarchy to asymptotic complexity (big O), so if an operation for fixing a cache miss takes higher time complexity, he takes that instead of O(1).
Similar happens when you write an O(1) algorithm while relying on malloc(), which is usually O(n log n), thus your algorithm is not really O(1), but O(n log n).
- lorenzhs 10y agoWhat's your n? The amount of memory allocated? In that case, I'd be interested to see such an algorithm that takes time O(1) but touches O(n) memory cells in the process... Obviously you need to include the time your calls take in the analysis, but your example seems ood.