Re: pop3 speedup

[Matthias Andree <ma@dt.e-technik.uni-dortmund.de>]

Am 26.09.2011 21:29, schrieb Lars Magne Ingebrigtsen:
> Matthias Andree <ma@dt.e-technik.uni-dortmund.de> writes:
> 
>> _exponential_? How does an algorithm for POP3 mail fetching with such a
>> complexity look like?
> 
> The old algorithm counted all the messages in the buffer from the start
> repeatedly while waiting for them all to arrive.  So if you fetched 1000
> messages, it would typically first count 10 messages, then it would
> count 20, then it would count 30, all the way up to 1000.
> 
> Hm.  Is that exponential?

No, squared, which is worse enough in this case. :-)

Watch (disregard small constant factors such as 2 or 1/2 or 5, only the
asymptotical growth matters):

n       n log n   n^2                 2^n
linear  lin-log   squared         exponential (base 2 here)

   3       5           9                   8
   5      12          25                  32
  10      33         100               1,024
  30     147         900       1,073,741,824
 100     664      10,000             1.26E30
1000   9,965   1,000,000            1.07E300

>> I've seen various awkward cases in POP3 or IMAP clients as worse as
>> O(n^2 * log n), but I can't possibly fancy how to attain O(e^n).
> 
> I know, I'm pretty awesome.  :-)

O(n^2) code is easily written (two nested loops with similar upper
bound) and quickly hurts when trying to scale software from the test
beds -- but you've got company there.  Some algorithms, such as checking
UID lists for "POP3 + leave messages on server", can't get better than
O(n log n) which is why I included that above.

-- 
Matthias Andree