Actually, O(n * m), where m is the - limited - length of the UID strings, and in practice, few comparisons are claimed to be necessary on the average case, on many servers, UID are either very short or share common prefixes.
It feels a lot faster at any rate with some 10,000 messages in the upstream server's mailbox, where my computer got quite slow already.
