In this paper we address de problem of algorithmic complexity relative to object recognition through indexing of local descriptors. Indeed, recent work has shown the possible advantages of these recognition techniques which are generally robust and efficient. Although they appear to be potentially very fast, our study shows that the overall complexity of the method is quadratic in the number of local descriptors per image, raising the question of the usefulness of these approaches for large indexing bases of complex images. We show, however, that a careful choice of descriptors may sufficiently reduce the inherent overhead in real applications. As a result we advance that it is more useful to use high-dimensional local descriptors which may be less discriminative, rather than lower-dimensional descriptors with a high expressive value to achieve an optimal recognition result.