Check Your Understanding

The decomposition tree has depth $O(\log n)$ because each centroid removal halves the maximum component size. If you start with $n$ nodes, after one level you have components of size at most $n/2$. After two levels, at most $n/4$. After $k$ levels, at most $n/2^k$. When the size reaches $1$, you stop. This logarithmic depth is why Centroid Decomposition is efficient. Quiz: For a tree with $1000$ nodes, what is the maximum depth of the decomposition tree?

Use the formula $n/2^k = 1$.

Space complexity is $O(n)$ for the data structures used.