Nah, that O(√N) comment in the article is a link to another blog post where the author claims that random memory accesses take O(√N) time. I say "claim" becaus

Nah, that O(√N) comment in the article is a link to another blog post where the author claims that random memory accesses take O(√N) time. I say "claim" because everything can be made to look like a fit on a log-log-plot. It's just memory hierarchy. (TLB misses do incur a logarithmic delay, because the page table usually uses a tree data structure, albeit with a high branching factor).