During steady walking, gait parameters fluctuate from one stride to another with complex fractal patterns and long-range statistical persistence. When a metronome is used to pace the gait (sensorimotor synchronization), long-range persistence is replaced by stochastic oscillations (anti-persistence). Fractal patterns present in gait fluctuations are most often analyzed using detrended fluctuation analysis (DFA). This method requires the use of a discrete times series, such as intervals between consecutive heel strikes, as an input. Recently, a new nonlinear method, the attractor complexity index (ACI), has been shown to respond to complexity changes like DFA, while being computed from continuous signals without preliminary discretization. Its use would facilitate complexity analysis from a larger variety of gait measures, such as body accelerations. The aim of this study was to further compare DFA and ACI in a treadmill experiment that induced complexity changes through sensorimotor synchronization.