On the maximum computing time of the bisection method for real root isolation. (March 2017) - Collins, George E.
Abstract: The bisection method for polynomial real root isolation was introduced by Collins and Akritas in1976 . In1981 Mignotte introduced the polynomials A a, n ( x ) = x n − 2 ( a x − 1 ) 2, a an integer, a ≥ 2 and n ≥ 3 . First we prove that if a is odd then the computing time of the bisection method when applied to A a, n dominates n 5 ( log ⁡ d ) 2 where d is the maximum norm of A a, n . Then we prove that if A is any polynomial of degree n with maximum norm d then the computing time of the bisection method, with a minor improvement regarding homothetic transformations, is dominated by n 5 ( log ⁡ d ) 2 . It follows that the maximum computing time of the bisection method is codominant with n 5 ( log ⁡ d ) 2 .