Since both of these 'referent set composition' operations at the conjunctive nodes -as well as the union operation at the disjunctive nodes -are linear in space and time on the number of elements in each of the composed sets (assuming the sets are sorted in advance and remain so), the calculation of referent sets only adds a factor of ¤ § ¤ to the size complexity of the forest and the time complexity of processing it, where ¤ § ¤ is the number of objects and events in the run-time environment.
the total space and time complexity of the above algorithm (on a context-free forest) is .