> Online dictionaries are likely to be backed by, well, a dictionary, which allows for O(1) look-ups.

I think that this is true only under simplifying assumptions of a sort that would also allow one to claim that dictionary look ups are O(1) (with constant equal to the size of the dictionary).