what do you mean by O(degree(vertex))?
beside consider that EVERY pair in relation must be checked to have a reverse. so for each pair of |R| members of relation, there is going to be a search. the search itself -if not using any tricks- is about visiting |R| pairs , so it does make sense that in worst case it would be of |R|*|R|