A tight time complexity for the procedure is not easy to come by, however, if we consider M to be the number of extensible maximal motifs and S to be the size of the output – i.e. the sum of the sizes of the motifs and the sizes of the corresponding location lists – then the time taken by the algorithm is O(SM log M). In experiments of the kind described later in the paper, at 3 GHz clock, time ranged typically from few minutes to half an hour.