Nested dissection gives the stated work and factor-storage bounds on regular grids

If a box side has length $m\ge 2$, the median rule leaves each child side with length at most $\lceil m\mathrm{/}2\rceil$; a side of length $1$ stays $1$. Iterating gives side lengths at depth $r$ at most $s_r=\lceil k\mathrm{/}{2}^r\rceil$. There are at most $2^{dr}$ boxes at that depth because each box has at most $2^d$ children. By depth $R=\lceil {\log }_{2}k\rceil$, every side has length $1$, so all remaining boxes are terminal. For $0\le r\le R$, $k\mathrm{/}{2}^r\ge 1\mathrm{/}2$, hence $s_r\le 2k\mathrm{/}{2}^r$.

If $k=1$, the grid and its ordering contain one terminal pivot and its factor column contains only the diagonal. Hence $d_v=1$ for its unique vertex, and [F4] gives $O(1)$ work and exactly one stored factor entry.

Let $G^{\mathrm{\prime }}$ be the structural graph of $A$ and let $G$ be the full nearest-neighbor grid on the same vertices. They use the same coordinate ordering. If a pair is an edge in a filled graph of $G^{\mathrm{\prime }}$, [F3] supplies a witness walk in $G^{\mathrm{\prime }}$ with internal vertices eliminated earlier; since $G^{\mathrm{\prime }}$ is a subgraph of $G$, the same walk witnesses that edge in the corresponding filled graph of $G$. Thus every later filled neighbor in $G^{\mathrm{\prime }}$ is also one in $G$, and each subgraph column size is at most the full-grid column size. Fix a box at depth $r$. Its separator has at most $d{s}_r^{d-1}$ vertices by the union bound over its at most $d$ median hyperplanes; the terminal singleton satisfies the same bound. By [F2], each such pivot has full-grid column size at most $3d{s}_r^{d-1}$, so the same bound holds for $A$.

The factorization work contributed by one depth-$r$ box is therefore at most a constant depending only on $d$ times $s_r^{d-1}{s}_r^{2(d-1)}=s_r^{3(d-1)}$, using [F4]. Summing over at most $2^{dr}$ boxes at each depth and using $s_r\le 2k\mathrm{/}{2}^r$ gives $O\text{\hspace{0.17em}⁣}\left(k^{3(d-1)}{\sum }_{r=0}^R{2}^{-r(2d-3)}\right)\mathrm{.}$ For $d=2$, the geometric ratio is $2^{-1}$, so this is $O(k^3)$. For $d=3$, the ratio is $2^{-3}$, so it is $O(k^6)$.

The storage contributed by one depth-$r$ box is at most a constant times $s_r^{d-1}{s}_r^{d-1}=s_r^{2(d-1)}$, again by [F2] and [F4]. Summing over boxes and using $s_r\le 2k\mathrm{/}{2}^r$ gives $O\text{\hspace{0.17em}⁣}\left(k^{2(d-1)}{\sum }_{r=0}^R{2}^{-r(d-2)}\right)\mathrm{.}$ For $d=2$, there are $O(\log k)$ equal-order terms, giving $O(k^2\log k)$. For $d=3$, the series is bounded by ${\sum }_{r\ge 0}{2}^{-r}=2$, giving $O(k^4)$.

When $d=2$, $n=k^2$ gives $k^3=n^{3\mathrm{/}2}$ and $k^2\log k=O(n\log n)$ for $k\ge 2$. When $d=3$, $n=k^3$ gives $k^6=n^2$ and $k^4=n^{4\mathrm{/}3}$. Thus steps 1.2, 2.1 and 2.2 give the displayed rates and the $k=1$ case. The proof used the coordinate-box and grid-boundary counts in [F1]–[F2] together with the fill containment proved in step 1.3, so it does not imply a bound for arbitrary graphs.