On the complexity of the Lickteig–Roy subresultant algorithm

In their 1996 article, Lickteig and Roy introduced a fast “divide and conquer” variant of the subresultant algorithm which avoids coefficient growth in defective cases. The present article concerns the complexity analysis of their algorithm over effective rings endowed with the partially defined division routine. We achieve essentially the same kind of complexity bound as over effective fields. As a consequence we obtain new convenient complexity bounds for gcds, especially when coefficients are in abstract polynomial rings where evaluation/interpolation schemes are not supposed to be available.