On other hand, condition (b) requires one search through P for every path element p ∈ P in the worst case, which is O(n 4 ).
the time complexity for get tier is O(|Σ|(n 2 + n 4 )) = O(n 4 ) since |Σ| is a constant.