Step detection is a common application in battery driven wearables. It enables fitness tracking as well as indoor localization. However, current state of the art approaches heavily rely on spectral properties of the acceleration signal or decision-strees comparing peaks and valleys, using various thresholds and timings. This requires accurate AD conversion as well as complex calculations to the disadvantage of battery life. Consequently, an ultra-low complexity step detector with competitive accuracy is desirable. We propose a zero-crossing interval and Bayesian-analysis based step detection algorithm which requires minimal computation at runtime, using a-priori knowledge from pre-computed statistical analysis. We compare our approach to a classifier that uses the more accurate but costly spectral properties of the data. The statistical analysis for pre-computation as well as evaluation is done using the annotated sensor data of the OU-ISIR Gait Database. Our evaluation shows the presented method outperforms classification with spectral features and delivers a step count accuracy that is competitive with state of the art commercial products.