minimal operations to solve a tridiagonal matrix $ A \in \mathbb{R}^{n x n} $ of a tridiagonal matrix and $b \in \mathbb{R}^{n}$
What is the least number of arithmetic statements as a function of n to solve $A*x = b$?
$$
\left( \begin{matrix}
a_{1,1} &  a_{1,2}  & 0 & \ldots & 0\\
a_{2,1}  &  a_{22} & a_{2,3} & \ldots & \vdots\\
0 & a_{3,2} &  \ddots &\ddots & 0\\
\vdots & \ddots &   \ddots     &   \ddots  & a_{n-1,n}\\
0 & \ldots & 0 & a_{n,n-1} & a_{n,n}
\end{matrix} \right)
$$
for LU  in 4x4 tridiagonal matrix I need 3 to zero operations -> n-1 for LU decomposition
Gaussian Elimination: $((n-1)n(n+1))/3 + ((n-1)n)/2$ subtractions/Multiplications  and   $(n(n+1))/2$  divisions.
Are the first steps correct? 
What is the correct solution?
Thanks.
 A: For a banded system of size $N$ with bandwidth $B$, the cost is $\mathcal{O}(B^2 N)$.
For a triangular system of size $N$ with bandwidth $B$, the cost is $\mathcal{O}(N^2)$.
For a complete linear dense system of size $N$, the cost is $\mathcal{O}(N^3)$.
In general, you should never do a naive gaussian elimination when you have some sparsity structure.
Here is a link with the costs for different sparse matrices
A: Not quite - using Gaussian elimination naively ends up drastically increasing the number of steps required. Naive Gaussian Elimination accounts for clearing every single non-diagonal element. But here, they are already clear in all but two other diagonals!
Because this has the feel of a homework question in a numerical analysis course, I won't give an explicit answer. (If it is a homework question, you should tag it as such). But I will say that it is possible to solve the system in less than 6n (even 5n, if you are witty) operations. That's not $n^2$!
HINT
Now, to get to the solution, think of modifying Gaussian Elimination so that you don't attempt to clear out empty values. Try it on a 5 by 5 matrix or something, and count how many operations you need then.
