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