The function is recursively called exactly once on each node of the dendrogram, leading to \(\mathcal {O}(n)\)  evaluations of the elementary quality function \(q_{\alpha }\) . Each call also evaluates a sum and a maximum operation on piecewise affine functions encoded by the list of their particular points \((\alpha _i, Q^{\Pi _{\mathcal {C}_i}}_{max}(\alpha _i))\) . These operations are done in time linear in the size of the input piecewise functions, the sum of their sizes is at most \(|\mathcal {C}|\) . Therefore this additional complexity is represented by the sum over all the nodes of the dendrogram of operations in \(\mathcal {O}(|\mathcal {C}|)\) . We can notice that this sum is nothing else than the path length of the hierarchical tree structure of community. Classical analysis show that the path length is between \(n\log (n)\)  and \(n^2\)  with an average value (over all trees of size \(n\) ) in \(\mathcal {O}(n\sqrt{n})\)  [1]}.
