By backward and forward substitutions we calculate the inverse of a triangle. How far is it better than the determinant method concerning the running time?
Inverse, if exists, of a triangular matrix is triangular. The determinant is multiplication of diagonal element. Therefore time complexity for determinant is o(n) and for inverse is o(n*n).
It is almost always a bad idea to compute the inverse matrix using the determinant method (Cayley–Hamilton method).
The determinant of a triangular matrix can indeed be computed in O(n) time, if multiplication of two numbers is assumed to be doable in constant time.
By simple backward and forward substitution no O(n*n) rumming time for the inverse matrix of a triangluar matrix can be achieved. The simple algorithms still have O(n^3) complexity. See e.g.
http://www.iaeng.org/publication/WCE2012/WCE2012_pp100-102.pdf
for more sophisticated algorithms.
Dear Professor,
We will be very pleased if you mention the detailed explanation of having O(n*sqrt(n)) .
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics