  Given two structures $G$ and $H$ distinguishable in $\fo k$ (first-order
logic with $k$ variables), let $A^k(G,H)$ denote the minimum alternation depth
of a $\fo k$ formula distinguishing $G$ from $H$. Let $A^k(n)$ be the maximum
value of $A^k(G,H)$ over $n$-element structures. We prove the strictness of the
quantifier alternation hierarchy of $\fo 2$ in a strong quantitative form,
namely $A^2(n)\ge n/8-2$, which is tight up to a constant factor. For each
$k\ge2$, it holds that $A^k(n)>\log_{k+1}n-2$ even over colored trees, which is
also tight up to a constant factor if $k\ge3$. For $k\ge 3$ the last lower
bound holds also over uncolored trees, while the alternation hierarchy of $\fo
2$ collapses even over all uncolored graphs.
  We also show examples of colored graphs $G$ and $H$ on $n$ vertices that can
be distinguished in $\fo 2$ much more succinctly if the alternation number is
increased just by one: while in $\Sigma_{i}$ it is possible to distinguish $G$
from $H$ with bounded quantifier depth, in $\Pi_{i}$ this requires quantifier
depth $\Omega(n^2)$. The quadratic lower bound is best possible here because,
if $G$ and $H$ can be distinguished in $\fo k$ with $i$ quantifier
alternations, this can be done with quantifier depth $n^{2k-2}$.
