ON THE COMPLEXITY OF AN ALGORITHM FOR INTEGER VECTOR CONVELUTIONS
关于整数向量卷积的一个算法的时间复杂度

The complexity of the conventional algorithm for cyclic convolution of twon-vectors with integer entries is O(n~2). Wu and Jiang 1] give an "optimal"algorithm with "complexity" O(n). In this paper we conclude that the complexityof their algorithm is not lower than O(n~2 log_2 n), so it is worse than the conve-ntional algorithm.