LU decomposition of tridiagonal matrix with pivoting LU decomposition of a tridiagonal matrix (matrix $A \in \mathbb R^{n,n}$ is tridiagonal iff $a_{i,j} = 0$ for $|i-j|$ > 1) when no pivoting is required ($A = LU$) can be done efficiently, because both $L$ and $U$ are bidiagonal and can be easily computed (like here: http://www.webpages.uidaho.edu/~barannyk/Teaching/LU_factorization_tridiagonal.pdf)
However, if pivot matrix is required ($PA=LU$), then $L$ nor $U$ have to be bidiagonal (example).
How to efficiently compute $P, L, U$ for tridiagonal matrix?

In the example you have $A=PLU$, i.e. $PA=LU$ so $PA$ is not tridiagonal anymore. However, PA is still banded matrix and can be effectively solved. The idea is very similar to the tridiagonal case. This is still an LU based algorithm, but concentrated to run inside the band.
The efficiency is therefore depends on the width of the band, i.e. a distance between farthest diagonals. One example of such algorithms is SPIKE.
You can also read this one.
I think I've seen an $O(nk)$ algorithm here.
