[marcosdumay]

You are correct in that the OP used the wrong metric. He should have written a big omega, not a big O.

> PCBs and integrated circuits are basically two-dimensional.

Yes, what pushes the complexity into Ω(n^1/2), that fits the original claim.

> Access times are limited by things like trace lengths

Again, Ω(n^1/2)

> and parasitics

And those are Ω(n)

So, as you found, on practice it's much worse, but the limit on the article is also there.