In this paper, we provide polynomial bounds on the worst case bit-complexity of two formulations of the continued fraction algorithm. In particular, for a square-free integer polynomial of degree n with coefficients of bit-length L, we show that the bit-complexity of Akritas’ formulation is O˜(n8L3), and the bit-complexity of a formulation by Akritas and Strzeboński is O˜(n7L2); here O˜ indicates that we are omitting logarithmic factors. The analyses use a bound by Hong to compute the floor of the smallest positive root of a polynomial, which is a crucial step in the continued fraction algorithm. We also propose a modification of the latter formulation that achieves a bit-complexity of O˜(n5L2).