Computational complexity analysis of least-squares Monte Carlo (LSM) for pricing US derivatives

One of the most important problems in option pricing theory is the valuation and optimal exercise of derivatives with American-style exercise features. These types of derivatives are found in all major financial markets. Simulation is a promising alternative to traditional numerical methods and has many advantages as a framework for valuing American options. Recently, Longstaff and Schwartz presented a simple, yet powerful, least-squares Monte Carlo (LSM) algorithm to approximating the value of US options by simulation. This article provides computational complexity analysis of the LSM algorithm. Essentially, the technique of computational complexity analysis is to break down a computational algorithm into logical modules and analyze the effect on the algorithm of adding or deleting logical modules. Computational complexity analysis is important in algorithm design because of structural differences in computer and human logic. Algorithms that seem perfectly natural and logical from the human perspective may sometime be found to contain unnecessary complexity when analysed from the computer's perspective. The results showed that a new algorithm constructed by removing the least-squares module altogether from the LSM algorithm improves not only the computational speed, but also produces results that are more accurate than the LSM.