Treffer: The complexity of late-binding in dynamic object-oriented languages.

We study the algorithmic complexity of supporting late binding in dynamic object-oriented programming (OOP) languages—i.e., languages that allow creation of new class definitions at runtime. We propose an abstraction of the late-binding problem for dynamic OOP languages in terms of operations on dynamic trees, and develop a lower bound of Ω(lg n) per operation (where n is the number of nodes in the tree). This result shows that efficient solutions (i.e., solutions that incur a constant time overhead per operation) of this problem are, in general, not possible. We also propose new data-structures and algorithms for solving the late-binding problem for dynamic OOP languages very efficiently, with a worst-case time complexity of $$O\left( {\sqrt[3]{n}} \right)$$ per operation. This result is an improvement over most existing approaches. [ABSTRACT FROM AUTHOR]