Calculating a polynomial's coefficients from its roots
For every integer $i$, $0\le i\le n$, let 
$$P_i(X) = (X-x_1)(X-x_2)\cdots(X-x_i)=a_{i,i}X^i+a_{i,i-1}X^{i-1}+\cdots+...+a_{i,0}$$
for some $a_{i,k}$, $0\le k\le i$. In particular, $a_{i,i}=1$. Expanding $P$ on both sides of the following equation and comparing the coefficients, 
$$P_{i+1}(X) = P_i(X)(X-x_{i+1})$$
we see that for $1\le k\le i\lt n$, 
$$a_{i+1,k}=-a_{i,k}x_{i+1}+a_{i,k-1}$$
and
$$a_{i+1,0} = -a_{i,0}x_{i+1}$$
So for fixed $i$, we can compute all coefficients of $P_{i+1}(X)$ from the coefficients of $P_i(X)$ with $O(i)$ steps. Now you should be able to see that your professor's suggestion on the minimum asymptotic complexity makes a lot of sense.