We propose a computationally highly scalable online anomaly detection algorithm for time series, which achieves - with no parameter tuning- a specified false alarm rate while minimizing the miss rate. The proposed algorithm sequentially operates on a fast streaming temporal data, extracts the nominal attributes under possibly varying Markov statistics and then declares an anomaly when the observations are statistically sufficiently deviant. Regardless of whether the source is stationary or non-stationary, our algorithm is guaranteed to closely achieve the desired false alarm rates at negligible computational costs. In this regard, the proposed algorithm is highly novel and appropriate especially for big data applications. Through the presented simulations,we demonstrate that our algorithm outperforms its competitor, i.e., the Neyman-Pearson test that relies on the Monte Carlo trials, even in the case of strong non-stationarity.