As is well known, options and other financial derivatives acquire their value from the underlying assets such as stocks and bonds and are traded extensively in the financial markets. We consider the problem of pricing an American option, that is an option with an early exercise feature. This problem can be formulated as an optimal stopping time problem for stochastic processes. In high dimensions, typically no closed form solution is available for American option prices and numerical methods relying on solving associated partial differential equations are also not viable. Recently there has been considerable research in developing simulation methods to solve this optimal stopping time problem via approximate dynamic programming. We overview commonly used pricing methods that use nested simulation and regression based techniques. We propose a new pricing algorithm wherein nearest neighbor estimator is used to estimate the continuation value functions required for the American option pricing. We derive asymptotic mean square error (MSE) of the option price estimator and find the optimal parameter for the nearest neighbor estimator that minimizes this MSE. This asymptotic MSE decays to zero as the allocated computational effort increases to infinity. We also discuss the impact of dimensionality on this rate of convergence.