Complexity of LUP decomposition of tri-diagonal matrix to solve an equation? Doing LU decomposition of tri-diagonal matrix and then solving the eqn by using forward substitution followed by backward substitution is done is O(n) time.
http://www.cfm.brown.edu/people/gk/chap6/node13.html
But what are the number of operations and the time complexity of LUP decomposition of tri-diagonal matrix?

LU factorization with partial pivoting for banded matrices of size $n\times n$ with bandwidth $w$ (number of subdiagonals plus number of superdiagonals) requires $O(w^2n)$ flops, triangular solvers require $O(wn)$ flops.
Thus, solving linear equations with tridiagonal matrix using LU factorization with partial pivoting also can be done in $O(n)$ floating point operations.
