  Let $G$ be a graph on $n$ vertices, with complement $\overline{G}$. The
spectral gap of the transition probability matrix of a random walk on $G$ is
used to estimate how fast the random walk becomes stationary. We prove that the
larger spectral gap of $G$ and $\overline{G}$ is $\Omega(1/n)$. Moreover, if
all degrees are $\Omega(n)$ and $n-\Omega(n)$, then the larger spectral gap of
$G$ and $\overline{G}$ is $\Theta(1)$. We also show that if the maximum degree
is $n-O(1)$ or if $G$ is a join of two graphs, then the spectral gap of $G$ is
$\Omega(1/n)$. Finally, we provide a family of connected graphs with connected
complements such that the larger spectral gap of $G$ and $\overline{G}$ is
$O(1/n^{3/4})$.
