In a self-attention mechanism processing a sequence of length $n$, the query, key, and value matrices each have dimensions $n imes d$. The scaled dot-product attention computes the product of an $n imes d$ matrix with a $d imes n$ matrix, and then multiplies the resulting $n imes n$ matrix by an $n imes d$ matrix. This yields a total computational complexity of $\mathcal{O}(n^2d)$. Since every token is directly connected to every other token, the computation requires only $\mathcal{O}(1)$ sequential operations (enabling full parallelization), and the maximum path length is the shortest possible at $\mathcal{O}(1)$.