Abstract
Options can be priced by the lattice model, the results of which converge to the theoretical option value as the lattice’s number of time steps
n
approaches infinity. The time complexity of a common dynamic programming pricing approach on the lattice is slow (at least
O
n
2
), and a large
n
is required to obtain accurate option values. Although
O
n
-time combinatorial pricing algorithms have been developed for the classical binomial lattice, significantly oscillating convergence behavior makes them impractical. The flexibility of trinomial lattices can be leveraged to reduce the oscillation, but there are as yet no linear-time algorithms on trinomial lattices. We develop
O
n
-time combinatorial pricing algorithms for polynomial options that cannot be analytically priced. The commonly traded plain vanilla and power options are degenerated cases of polynomial options. Barrier options that cannot be stably priced by the binomial lattice can be stably priced by our
O
n
-time algorithm on a trinomial lattice. Numerical experiments demonstrate the efficiency and accuracy of our
O
n
-time trinomial lattice algorithms.