An upper bound on the average number of iterations of the LLL algorithm

AbstractAn upper bound is established regarding the average number of iterations of the lattice reduction algorithm of Lenstra, Lenstra and Lovász (the LLL algorithm). The upper bound is of the form O(n2 log n), where n is the dimension of the problem. It is essentially independent of the length of the input vectors, so that, in any fixed dimension, the LLL algorithm turns out to be of complexity O(1) on average