You also get a hint from direction changes. As far as I can tell, direction changes almost always indicate that the current letter is in the word, though not every letter gets a direction change.

The first thing that came to mind was "Newton," which used stroke-recognition for recognizing letters. I doubt it's actually computing letters on the fly, I go along with your thought that you precompute vectors for each word in the dictionary. My thought is that the vectors are probably very simple. They may start with a specific letter, but after that I'm guessing they are very forgiving of inaccuracies. A rough direction and distance is probably enough to disambiguate words from each other.

I'm guessing it precomputes a tree for the dictionary. With each stroke, it drills down the tree along the most likely path. If it runs out of nodes, it backtracks and tries a more likely path somewhere,possibly using a precomputed list of vectors most likely to be mistaken for each other.

That gives On for the best case.

I doubt they use bloom filters (or any other hash-based algorithm) because hashes by their design are a quick way to reference something well defined. A gesture is anything but and you need something a lot more fuzzy and flexible than hashes.

I'd think that they try to calculate the focus of each direction change and see what letter it landed on, then try a fuzzy match to words that have the smallest hamming distance between their input. After you get a good approximation of all the letters, then you can try hashing techniques.

Also, pivoting on first and last letter of each word isn't fool-proof, as the first and last letters are also not guaranteed to be hit dead-on.

I would have to go with what Natrius said. It's probably based on the stroke directions. The technology is probably very similar to that used to recognize Chinese writing.