I did basic voice recognition on an Atari ST (8MHz 68000, 8-bit mono sampling1). If it could be done on a 1985 desktop2 then it should be no problem for an early naughties cell-phone3.
IIRC4, the algorithm was roughly as follows:
Sample the audio (8-bit mono @ 22kHz?)
Split the audio into short (½ second?) pieces
Do an FFT on each piece. The results are ...