Complexity of 3 matrix multiplications 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 ?
 A: 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.
A: 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.
