> with O(1) expected restructuring time and exponentially infrequent occurrences of expensive restructuring

So I was curious about this, so I threw together a quick and dirty implementation of the insert function as described in the paper, counting both the number of times the insert() function is called and the number of times a pointer is written to when inserting 65535 (2^16 - 1) random numbers:

Below are the results:

    Inserts      0 to      1: Avg fn calls:   2.00, Avg ptr writes:   2.00 
    Inserts      1 to      3: Avg fn calls:   3.50, Avg ptr writes:   1.00 
    Inserts      3 to      7: Avg fn calls:   5.00, Avg ptr writes:   4.00 
    Inserts      7 to     15: Avg fn calls:   6.12, Avg ptr writes:   5.00 
    Inserts     15 to     31: Avg fn calls:   7.06, Avg ptr writes:   4.62 
    Inserts     31 to     63: Avg fn calls:   7.28, Avg ptr writes:   3.59 
    Inserts     63 to    127: Avg fn calls:   9.64, Avg ptr writes:   4.81 
    Inserts    127 to    255: Avg fn calls:  11.72, Avg ptr writes:   4.08 
    Inserts    255 to    511: Avg fn calls:  13.73, Avg ptr writes:   4.73 
    Inserts    511 to   1023: Avg fn calls:  17.61, Avg ptr writes:   5.30 
    Inserts   1023 to   2047: Avg fn calls:  18.95, Avg ptr writes:   4.99 
    Inserts   2047 to   4095: Avg fn calls:  19.12, Avg ptr writes:   5.05 
    Inserts   4095 to   8191: Avg fn calls:  19.67, Avg ptr writes:   4.98 
    Inserts   8191 to  16383: Avg fn calls:  20.76, Avg ptr writes:   4.94 
    Inserts  16383 to  32767: Avg fn calls:  22.38, Avg ptr writes:   4.99 
    Inserts  32767 to  65535: Avg fn calls:  24.18, Avg ptr writes:   4.99 

So it turns out that it is O(1) in terms of number of pointer writes but O(lg(n)) in terms of number of function calls, and since every function call will perform at least one comparison, that means this algorithm is O(1) for writes but O(lg(n)) for reads, meaning that given large enough n, the O(lg(n)) read term will dominate and thus this algorithm is O(lg(n)) for inserts.

That said, if writes are far more expensive than reads in the context this is used, this could still be useful.