NFA and DFA storage cost
Consider the construction of an NFA from a regular expression $r$. The construction is by induction over the generating sequence of $r$. If you examine the different operations (union, Kleene star, and concatenation), you will see that each operation increases the size of the NFA by a linear blowup. 

For example, an NFA for $r_1\cup r_2$ is obtained by nondeterministically starting in an NFA for $r_1$ or an NFA for $r_2$, so the size of the NFA is (by induction) at most $|r_1|+|r_2|$.

Now, determinizing an NFA with $k$ states may involve a blowup of up to $2^k$ states. However, the NFA you obtained from the construction has $k=O(n)$ states, so the blowup is $2^{O(n)}$. The paper you read shows that the $O(n)$ factor is in fact $n\cdot O(\log|\Sigma|)$, thus making the total size $O(|\Sigma|^n)$.