  Let $S_{a,b}$ denote the sequence of leading digits of $a^n$ in base $b$. It
is well known that if $a$ is not a rational power of $b$, then the sequence
$S_{a,b}$ satisfies Benford's Law; that is, digit $d$ occurs in $S_{a,b}$ with
frequency $\log_{b}(1+1/d)$, for $d=1,2,\dots,b-1$.
  In this paper, we investigate the \emph{complexity} of such sequences. We
focus mainly on the \emph{block complexity}, $p_{a,b}(n)$, defined as the
number of distinct blocks of length $n$ appearing in $S_{a,b}$. In our main
result we determine $p_{a,b}(n)$ for all squarefree bases $b\ge 5$ and all
rational numbers $a>0$ that are not integral powers of $b$. In particular, we
show that, for all such pairs $(a,b)$, the complexity function $p_{a,b}(n)$ is
\emph{affine}, i.e., satisfies $p_{a,b}(n)=c_{a,b} n + d_{a,b}$ for all
$n\ge1$, with coefficients $c_{a,b}\ge1$ and $d_{a,b}\ge0$, given explicitly in
terms of $a$ and $b$. We also show that the requirement that $b$ be squarefree
cannot be dropped: If $b$ is not squarefree, then there exist integers $a$ with
$1<a<b$ for which $p_{a,b}(n)$ is not of the above form.
  We use this result to obtain sharp upper and lower bounds for $p_{a,b}(n)$,
and to determine the asymptotic behavior of this function as $b\to\infty$
through squarefree values. We also consider the question which linear functions
$p(n)=cn+d$ arise as the complexity function $p_{a,b}(n)$ of some leading digit
sequence $S_{a,b}$.
  We conclude with a discussion of other complexity measures for the sequences
$S_{a,b}$ and some open problems.
