[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Complexity of Topological Sort + single-pass treewalk tiebreaker



Let n be the number of classes at or above the one for which you which to
compute the CPL; let m be the sum of the number of direct superclasses at
each class at or above the class of interest.  You can do the tiebreaker
treewalk in O(n) time; the topological sort O(n+m), so the whole thing is
linear.

			-rpg-