By the fundamental theorem of symmetric polynomials, if $P \in \Q[X_1,\dots,X_n]$ is symmetric, then it can be written $P=Q(\sigma_1,\dots,\sigma_n)$, where $\sigma_1,\dots,\sigma_n$ are the elementary symmetric polynomials in $n$ variables, and $Q$ is in $\Q[S_1,\dots,S_n]$. We investigate the complexity properties of this construction in the straight-line program model, showing that the complexity of evaluation of $Q$ depends only on $n$ and on the complexity of evaluation of $P$. Similar results are given for the decomposition of a general polynomial in a basis of $\Q[X_1,\dots,X_n]$ seen as a module over the ring of symmetric polynomials, as well as for the computation of the Reynolds operator.