[eapriv]

Even this is not in any way related to the asymptotic time bounds discussed in the article.

[dlubarov]

Right - in case it's not clear to all, the square root metric Vitalik mentions is about measuring both proof size and verifier complexity. Neither the prover nor the verifier is doing any square root computations.