In MATLAB, you can get a 2d Laplacian via `A = delsq(numgrid('S',N));`

yielding a matrix $A$ that is $n \times n$ with $n = O(N^2)$, for a square domain discretized with an $N \times N$ grid.

Reviewing the literature, it is reiterated again and again that solving $Ax=b$ with nested dissection ordering takes $O(n\log n)$ space but $O(n^{1.5})$ FLOPS. Nevertheless, when one solves $Ax=b$ with MATLAB's backslash, one observes very robust $O(n)$ scaling, or maybe $O(n^{1.1})$:

MATLAB does not use nested dissection, it uses AMD, a variant of the minimum vertex order algorithm.

I'm reading all the literature that I can find on minimum vertex order algorithms. Every paper or book that I read, this algorithm is tested on some zoo of sparse matrices, and performance is measured experimentally, but I have not seen any big-O estimates for the 2d Laplacian.

Is there a big-O estimate for the 2d Laplacian? Can one really assert that MATLAB's sparse solvers work in $O(n)$ time on the 2d Laplacian? Also, what's the scaling for 3d Laplacians? I'm hoping this is somewhere in the classical literature, because if it isn't, it's probably because it's hard to answer.