Before revision: I.e. TSD construction takes with high probability {\cal O}( n \ln n) time and TSD size can be made worst case {\cal O}(n) with an expected rebuild cost of {\cal O}( 1).
After revision: I.e. TSD construction takes with high probability {\cal O}( \log^2 n) comparisons in the latter two DAGs. However, the expected depth of the DAGs and high probability bounds for their size are unknown. Using a novel analysis technique, we show that the three DAGs have w.h.p. i) a size of {\cal O}(n) with an expected rebuild cost of {\cal O}( 1).