Complexity of LUP decomposition of tri-diagonal matrix to solve an equation?

Question

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?

Answer 1

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.