Asymptotic complexity of the cross-correlation function?

Question

Algorithms

Interested in the upper bound O(???) for the VCF of discrete sequences of length l and k (for example, l is less than k) with a unit lag

Answer 1

Interested in the upper bound O(???) for the VCF of discrete sequences of length l and k (for example, l is less than k) with a unit lag

Offhand, Ο(k^2). I mean, the sequences are one-dimensional.
Imagine a window of width k, we will push a sequence of length l into it. There are k+l options in total. For each option, it is necessary to calculate the scalar product of the window content and the sequence of length k (complex conjugate to the original one), which will require Θ(k), or Ο(k). Multiplying, we discard the lower terms, we get Ο(k^2).