Query complexity on Quantum Pattern Matching of Mateus Algorithm

I am trying to understand the complexity of the Mateus and Omar algorithm for quantum pattern matching, it is clear to me from the pseudocode that the query complexity is $O(sqrt{N})$, apart from the cost of setting up the initial state:
$$
frac{1}{sqrt{N-M+1}}sum_{k=1}^{N-M+1}|k,k+1,…,k+M-1⟩
$$

After that, they conclude that the algorithm has an efficient compile time of $O(Nlog^{2}(N)times |Sigma|)$ and a total runtime of $O(Mlog^{3}(N)+N^{3/2}log^{2}log(M))$, but query complexity $O(sqrt{N})$.

My question is, if I devise an algorithm with, for example, a processing step of $O(N^{2})$ circuit complexity but $O(sqrt{N})$ query complexity. Is it completely fine to say that it is faster than a classical equivalent with, for example $O(N)$ complexity? I’m a bit stuck trying to figure this out.