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.
I 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.
Comments
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.
I 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.