  In this article we propose a Weighted Stochastic Mesh (WSM) Algorithm for
approximating the value of a discrete and continuous time optimal stopping
problem. We prove that in the discrete case the WSM algorithm leads to
  semi-tractability of the corresponding optimal problems in the sense that its
complexity is bounded in order by $\varepsilon^{-4}\log^{d+2}(1/\varepsilon)$
with $d$ being the dimension of the underlying Markov chain. Furthermore we
study the WSM approach in the context of continuous time optimal stopping
problems and derive the corresponding complexity bounds. Although we can not
prove semi-tractability in this case, our bounds turn out to be the tightest
ones among the bounds known for the existing algorithms in the literature. We
illustrate our theoretical findings by a numerical example.
