What does “standard conv2d” mean in this case? Are you referring to just calling F.conv2d as-is? Even with a single thread, this will typically dispatch to an MKLDNN implementation on many systems, which means it will use a highly optimized vectorized and memory-hierarchy-aware implementation. You are correct in that there will still be implicit parallelism here due to the use of vectorized instructions. On the other hand, even without parallelism, performance is going to be highly dependent on how the computation aligns with a CPU’s caches (which again is going to be highly optimized here).
So in practice, even if there is some theoretical complexity improvement, this improvement can often be difficult to realize given that different algorithms will often have different memory access patterns and different levels of vectorization friendliness. It becomes even more difficult to compare when the baseline is a highly tuned library implementation (as F.conv2d will use in this case).