  Shallit and Wang showed that the automatic complexity $A(x)$ satisfies
$A(x)\ge n/13$ for almost all $x\in{\{\mathtt{0},\mathtt{1}\}}^n$. They also
stated that Holger Petersen had informed them that the constant 13 can be
reduced to 7. Here we show that it can be reduced to $2+\epsilon$ for any
$\epsilon>0$. The result also applies to nondeterministic automatic complexity
$A_N(x)$. In that setting the result is tight inasmuch as $A_N(x)\le n/2+1$ for
all $x$.
