The bound is the same as for the reported algorithms for checking wellnestedness (Möhl, 2006).
the following theorem allows wellnestedness checking to be linear for projective trees, to be faster for random input, and to remain O(n 2 ).