Thus, the complexity of GRE in the gradable case is determined by three steps: The first is quadratic and can be performed off-line, the second has a worst-case running time of O(n v n a ), and the third one has a worst-case running time of O(n d n i ).
gradable GRE takes only polynomial time, and if we focus on the part that cannot be done off-line, it takes only linear time.