Suppose that I have a matrix $A$ of dimension $m \times m$, which can be computed as:
$$A= X D X^\top$$
where $X$ is a matrix of dimension $m \times n$, with $m > n$, and $D= \operatorname{diag}(d)$, with $d$ a vector $n \times 1$. I want to compute the computational complexity of creating matrix $A$. Because I can write matrix $A$ as the sum of outer products as:
$$A= \sum_{i=1}^n d_i x_i x_i^\top $$ where $x_i$ is the $i$th column of $X$. Since I am performing $n$ outer products of vectors with dimensions $m$, the overall computational complexity is $\mathcal{O}(mn)$.
Suppose now that each $x_i$ is a sparse vector, with only $n$ non-zero entries. Can I conclude that the computational complexity is $\mathcal{O}(n^2)$? I am having $n$ outer products of vectors whose dimension is $m \times 1$, but only $n$ entries are non zero.