·[Thm]Forp=N-(),PT(⑤=O(1)w.h.p -By our characterization,it's enough to consider complete binary tree. For p N-(1),each layer of tree shrinks the #1's by a factor of p. ·pN→pN→p3N→..→0：Only O(1)steps. ·Thm]Forp=o(N-67),TD(⑤=O(1)w.h.p. -Quite technical,omitted here.• [Thm] For p = N-Ω(1) , PT(f) = O(1) w.h.p. – By our characterization, it’s enough to consider complete binary tree. – For p = N-Ω(1), each layer of tree shrinks the #1’s by a factor of p. • pN → p 2N → p 3N → … → 0: Only O(1) steps. • [Thm] For p = o(N-6/7), TD(f) = O(1) w.h.p. – Quite technical, omitted here