# Precedence Table Construction Algorithm for CFGs Regardless of Being OPGs
## 4 Approach
### Complexity Analysis
#### 4.4.4 Complexity of Algorithm 5 (Table)  
According to the first **for-cycle**, the number of times it would be executed will be \(p\). Immediately following the previous one, the inner **for-cycle** is executed in the worst-case \(g\) times, assuming that the total number of grammatical symbols appear in each production. Therefore, the computational cost of the two cycles is \(\mathcal{O}(p\times g)\).  
The computational costs for the construction of \(\texttt{Left}(A)\), \(\texttt{Right}(A)\), and \(\texttt{Leftmost}(A)\), \(\forall A\in N\), are already computed. In computing the complexity of Table, the length of each generated set will be considered, which in the worst case is \(t\).  
The analysis of the four **if-blocks** inside the second **for-cycle** is as follows:  
* In the first **if-block**, after checking, the executed instruction is carried out in constant time and is denoted \(\mathcal{O}(1)\).
* In the second **if-block**, after checking, the first instruction is executed in a constant time \(\mathcal{O}(1)\), and the second is executed in a computational time \(\mathcal{O}(t)\); therefore, the computational time of the **if-block** is \(\mathcal{O}(t)\).
* In the third **if-block**, after checking, three sub-blocks are distinguished; the first one corresponds to the travel of \(\texttt{Right}(A)\), executed in a computational time \(\mathcal{O}(t)\). After checking \(u\
eq null\), the second sub-block presents two instructions executed in a constant time \(\mathcal{O}(1)\). The third sub-block, after the checking of \(l\
eq[\ ]\), presents a computational cost \(\mathcal{O}(n\times t)\), determined by the for-cycle executed, in the worst case, \(\mathcal{O}(n)\) times, corresponding to the number of non-terminal symbols in \(G\) and the travel it makes from \(\texttt{Right}(B)\) with a cost \(\mathcal{O}(t)\). In summary, the computational cost of the third **if-block** is \(\mathcal{O}(n\times t)\), corresponding to the worst case.
* In the fourth **if-block**, after checking, four sub-blocks are distinguished. The first corresponds to the combinations formed from traversing \(\texttt{Right}(A)\) and \(\texttt{Leftmost}(B)\) to obtain the precedence relations \(a\geqslant b\). Since the maximum size of each set is \(t\), the computational cost of these combinations is \(\mathcal{O}(t^{2})\). After checking \(u\
eq null\), the second sub-block presents an instruction where \(\texttt{Left}(B)\) is traversed; therefore, the computational cost is \(\mathcal{O}(t)\). In the third sub-block, after the checking of \(l\
eq[\ ]\), it presents a **for-cycle** that executes at most \(n\) times the combinations formed fromtraversing Right(\(C\)) and Leftmost(\(B\)) to obtain the precedence relations \(c>b\). These combinations are traversed maximally in \(\mathcal{O}(t^{2})\) computational time because \(t\) is the size of both sets and, consequently, the computational cost of the third sub-block is \(\mathcal{O}(n\times t^{2})\). The last sub-block will have a cost of \(\mathcal{O}(1)\). In summary, the computational cost of the fourth block is \(\mathcal{O}(n\times t^{2})\), corresponding to the worst case.  
In summary, the computational cost of the four **if-blocks** within the second **for-cycle** of Algorithm 5 is \(\mathcal{O}(n\times t^{2})\), this being the worst case; therefore, the computational cost of the main body of Algorithm 5 formed by the two nested **for-cycles** and the four **if-blocks** is \(\mathcal{O}(p\times g\times n\times t^{2})\) which is greater than the cost of computing any of the three sets of terminal symbols Left(\(A\)), Right(\(A\)), and Leftmost(\(A\)), \(\forall A\in N\), when starting the algorithm, and corresponding to \(\mathcal{O}(p)\).