Yea, I thought about that, but he doesn't mean theta, either. What he's giving is a physical impossibility proof -- you can't do memory access better than sqrt(N). When he gives a physical example of a machine of arbitrary size that accesses memory in sqrt(N) time, then we can talk about theta.
The speed of light limitation on distance to DRAM memory is real, but so far seems to affect mostly supercomputers. Are there any large server boards where speed of light lag is the limit on memory capacity?
