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?