# What is the cost of factorization for one-dimensional sparse problems?

In Golub and Van Loan's book, Matrix Computations, page 606, it is stated that:

With standard discretizations, 2-dimensional problems can be solved with $O(n^{3/2})$ work and $O(n \log{n})$ fill-in. For 3-dimensional problems, the typical costs are $O(n^2)$ work and $O(n^{4/3})$ fill-in.

Here, they refer to elliptic partial differential equation problems solved on a grid and $n$ refers to the number of unknowns. I guess it is trivial to calculate the cost (probably linear) for one-dimensional problems, but I don't know how to do that. I would appreciate any help for that.

It may help to define $N$, the number of discretization points along a 1D edge, and relate it to $n$, the number of unknowns in the system. In 2D on a square grid of points, $n = O(N^2)$. Nested dissection efficiently reduces the sparse system you usually get from discretizations by eliminating levels of "interior" points. The result is a more dense system the size of a few lines of "separator" points, which is of size $O(n^{1/2})$ and can be solved directly in $O(n^{3/2})$ time. The fill-in costs come from the fact that eliminating interior points at each level couples more points together (creating new connections in the matrix, hence fill-in).
The 3D costs come about similarly, except now $n = N^3$, and the separators are now planes with $O(N^2) = O(n^{2/3})$ points. Solving systems involving these planes then gives you the $O(n^2)$ cost).
However, for 1D problems, $n=N$, and you can order unknowns from left to right to get a tridiagonal system, which can be solved in $O(n)$ time with no fill-in with the Thomas algorithm.