I've find a way to get O(log(n)) as the worst case with any operation on the piece table. I've put a description in http://e98cuenc.free.fr/wordprocessor/piecetable.html
The main affected class will be pf_Fragments. In the web page (still not finished) I discuss all the gory details. Cheers,
