  Let $\mathrm{WP}_G$ denote the word problem in a finitely generated group
$G$. We consider the complexity of $\mathrm{WP}_G$ with respect to standard
deterministic Turing machines. Let $\mathrm{DTIME}_k(t(n))$ be the complexity
class of languages solved in time $O(t(n))$ by a Turing machine with $k$ tapes.
We prove that $\mathrm{WP}_G\in\mathrm{DTIME}_1(n\log n)$ if and only if $G$ is
virtually nilpotent. We relate the complexity of the word problem and the
growth of groups by showing that $\mathrm{WP}_G\not\in
\mathrm{DTIME}_1(o(n\log\gamma(n)))$, where $\gamma(n)$ is the growth function
of $G$. We prove that $\mathrm{WP}_G\in\mathrm{DTIME}_k(n)$ for strongly
contracting automaton groups, $\mathrm{WP}_G\in\mathrm{DTIME}_k(n\log n)$ for
groups generated by bounded automata, and
$\mathrm{WP}_G\in\mathrm{DTIME}_k(n(\log n)^d)$ for groups generated by
polynomial automata. In particular, for the Grigorchuk group,
$\mathrm{WP}_G\not\in\mathrm{DTIME}_1(n^{1.7674})$ and
$\mathrm{WP}_G\in\mathrm{DTIME}_1(n^2)$.
