Technically, the scenario described could happen entirely offline: voice recognition, transcription, then match for autocomplete (not that I am claiming this is what happened).
Full-text voice recognition is CPU intensive though, so one can expect mobile that's doing that all the time to drain its battery pretty fast in a noisy environment which should be rather obvious.