assuming that data is being inserted continuously at the same rate, periodic full compaction of an lsm tree with an upper bound on time between full compactions is O(n^2). depending on the quantity and distribution of deletes, you can potentially do much better with incremental compaction strategies while still maintaining an upper bound on the delay in processing a delete.