If I have 2 matrices
$X = [N \times D]$
$S = [N \times N]$
I read from https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations that the complexity of $X^TS$ would be $O(DN^2)$
What is the complexity of $X^TSX$ ? Since $X^TS$ is now a $[D \times N]$ matrix, is $X^TSX$ $O(DN^2 \times D^2N)$ ? Or can I do better ?
What if S is a diagonal matrix ?
You need to decide whether to compute $(X^TS)X$ or $X^T(SX)$. By symmetry this will turn out to be the same: $O(DN^2 + D^2N)$.
If $S$ is diagonal, and you take advantage of this fact (by implementing the multiplication via rescaling of rows), then $SX$ can be computed in $O(ND)$ time. The total cost of $X^T(SX)$ is then dominated by the cost of the second multiplication, $O(D^2N)$.
Finally, note that the above calculations assume naive matrix multiplication; algorithms exist that are (slightly) asymptotically faster.
The complexity informs us about the complexity of the algorithm, which in this case would be the most general one (Schoolbook matrix multiplication).
Say that you have two general matrices $A (m\times n)$ and $B (n\times p)$, then the product matrix $C=AB$ is computed with:
$$ c_{ij} = \sum_{k=1}^n a_{ik} \times b_{kj} $$
If you know nothing about $A$ and $B$, then the complexity can be no better than $O(mnp)$, because we have $mp$ elements in the $C$ matrix, which each took $n$ products.
Q1. To answer your question, if you have $Y=X^TSX$, and no more information about $S$, then we can analyze the formula to figure out the complexity:
$$ y_{ij} = \sum_{k=1}^N \sum_{l=1}^N x_{ki}\times s_{kl}\times x_{lj}$$
so in this case the complexity for $Y$ would be $O(D^2\times N^2 \times 2)$, because we have $D^2$ elements, with two $N$-sums of $2$ products each. The complexity could be lower if you stored the intermediate matrix product, instead of recomputing for each pair $(i,j)$. For example, one can precompute the matrix $(SX)_{k,j}$, whose values will be reused for the matrix-vector multiplications in the rest of the product: $\sum_{k=1}^N x_{ki}\times (SX)_{kj} $. This would yield a complexity of $O(DN(D+N))$, as user7530 explained.
Q2. With the formula above, the answer to your last question is straightforward. If $S$ is diagonal, then we are only interested in the $s_{kk}$ elements, which would cancel one of the sums, and factoring out the $s_{kk}$ term:
$$ y_{ij} = \sum_{k=1}^N x_{ki}\times s_{kk}\times x_{kj}$$
with complexity $O(D^2\times N \times 2)$. If you know more about $X$, you can further simplify your product.
