Quadratic relationship between nondeterministic and deterministic space?
In my paper with Domaratzki and Kisman, "On the number of distinct languages accepted by finite automata with n states" published in J. Automata, Languages, and Combinatorics 7 (2002) we proved that if $G_k (n)$ is the number of distinct languages accepted by NFA's with $n$ states over a $k$-letter alphabet, and $g_k (n)$ is similarly the number of distinct languages accepted by DFA's, then for fixed $k \geq 2$

(i) $\log g_k (n)$ is, up to smaller order terms, asymptotically $kn\log n$

(ii) $\log G_k (n)$ is, up to smaller order terms, asymptotically between $(k-1)n^2$ and $kn^2$.