  Population protocols are a distributed computing model appropriate for
describing massive numbers of agents with limited computational power. A
population protocol "has an initial leader" if every valid initial
configuration contains a single agent in a special "leader" state that helps to
coordinate the computation. Although the class of predicates and functions
computable with probability 1 is the same whether or not there is an initial
leader (semilinear functions and predicates), it is not known whether a leader
is necessary for fast computation. Efficient population protocols are generally
defined as those computing in polylogarithmic in $n$ (parallel) time. We
consider leaderless population protocols, regarding the computation finished
when a configuration is reached from which a different output is no longer
reachable.
  In this setting we show that a wide class of functions and predicates
computable by population protocols are not efficiently computable (they require
at least linear time to stabilize on a correct answer), nor are some linear
functions even efficiently approximable. For example, the widely studied
parity, majority, and equality predicates cannot be computed in sublinear time.
Moreover, it requires at least linear time for a population protocol even to
approximate any linear function with a coefficient outside of $\mathbb{N}$: for
sufficiently small $\gamma > 0$, the output of a sublinear time protocol can
stabilize outside the interval $f(m) (1 \pm \gamma)$ on infinitely many inputs
$m$. We also show that it requires linear time to exactly compute a wide range
of semilinear functions (e.g., $f(m)=m$ if $m$ is even and $2m$ if $m$ is odd).
  Finally, we show that with a sufficiently large value of $\gamma$, a
population protocol can approximate any linear $f$ with nonnegative rational
coefficients, within approximation factor $\gamma$, in $O(\log n)$ time.
