6 ms·
I don't think the claim is true in quite as much generality as the author claims. Some deterministic data structures use much more space than time, for example,
by randomizedalgs 3y ago
I don't think the claim is true in quite as much generality as the author claims. Some deterministic data structures use much more space than time, for example, the deterministic implementation of a Van Emde Boas tree.
- andrewp123 3y agoI think you're missing out on the time it takes to build the tree in the first place, which is O(M), equal the space complexity. People usually ignore this cost as a "preprocessing" factor, but it's a cost that's really there. After this initial O(M) time and space cost, you do additional operations which only take up time, not space, so the claim Time >= Space holds here as well.