actions is O(C n), where C is a constant.
3 One might think that computing the score of each new JOIN i j action would be expensive (because one might have the total runtime is O(n 2 log n) + O(sn log n), where s ≤ n is the number of actions popped before HALT and tends to be small.