## 5 Complexity  
In this section, the complexity of the algorithm is analysed from two different points of view: (i) regarding the size of the input BPMN model and (ii) regarding the number of pattern pairs in the repository.  
To carry out this analysis, the flow diagrams shown in Figure 11 will be used. These diagrams contain the basic behaviour of the algorithm with the most relevant operations from the point of view of time complexity. Firstly (see Figure 11a), the algorithm consists of a patterns loop that runs through the set of pairs of patterns within the repository. As explained in the Section 4, this loop is executed until no more patterns to simplify can be found. In this way, the number of executions of the loop depends on the complexity of BPMN model under consideration.  
In each execution of the patterns loop, each of the pairs of patterns is probed (with the search operation) for a possible replacement (see Figure 11a).  
The replacement of a pattern (Figure 11b) has a complexity of \(O(1)\) because its execution time does not depend on the size of the BPMN model or the number of patterns in the repository. The replacement operation involves simple modifications on the BPMN model, actually, just adjusting or deleting some  
Figure 10: Result after stage two.  
Figure 9: Architecture from second stage.  
BPMN elements. The reader can see on the Listing 2 the Java code responsible for the replacement of pattern A (lines 21-36).  
Regarding the search operation (Figure 11b,c), its complexity cannot be disregarded. The search for a possible simplifiable pattern needs to carry out a loop that checks each element included in the BPMN model. However, it is sufficient to go through the entire list of elements only once during a search operation. In each iteration the focus is on one BPMN element and its immediately adjacent elements (those connected directly with a sequence flow stereotype). The idea is to check if the relationship between the considered element and its adjacent elements is identical to the one expressed in the simplifiable pattern. These check operations have a complexity of \(O(1)\) (typically it will be a comparison between pairs of values) and their execution time does not depend on the size of the BPMN, nor the number of patterns in the repository. As the reader can note, the time consumption in this model is due to the search loop (Figure 11c), which only depends on the size of the BPMN model linearly.  
It is also worth noting that it is not uncommon for a BPMN model to show a tree-like design, i.e., to include many branches on its representation. On first thought, this could pose an issue for searching a particular fragment. However, to perform the search for the simplifiable pattern, and due to the model representation that the BPMN notation allows, it is not necessary to dive for the various bifurcations that a model can present. In fact, it is just required to check elements one by one, regardless of its position on the model, to evaluate the adjacent elements in order to verify if a simplifiable pattern can be spotted.  
Summing up, it can be stated that the search operation has a complexity \(O(n)\). The reader can check an example of a search operation on the Listing 2, which shows the Java code responsible for the search of pattern A (lines 3-18). The creation of the search loop (considering each element of Exclusive Gateway type) is shown on line 5. The number of iterations of this loop depends directly on the size of the BPMN model.  
Figure 11: Flow diagrams to analyse the complexity. (**a**) Algorithm flow diagram; (**b**) Patterns pair flow diagram; (**c**) Search simplifiable pattern.