  While many optimization problems work with a fixed number of decision
variables and thus a fixed-length representation of possible solutions, genetic
programming (GP) works on variable-length representations. A naturally
occurring problem is that of bloat (unnecessary growth of solutions) slowing
down optimization. Theoretical analyses could so far not bound bloat and
required explicit assumptions on the magnitude of bloat. In this paper we
analyze bloat in mutation-based genetic programming for the two test functions
ORDER and MAJORITY. We overcome previous assumptions on the magnitude of bloat
and give matching or close-to-matching upper and lower bounds for the expected
optimization time. In particular, we show that the (1+1) GP takes (i)
$\Theta(T_{init} + n \log n)$ iterations with bloat control on ORDER as well as
MAJORITY; and (ii) $O(T_{init} \log T_{init} + n (\log n)^3)$ and
$\Omega(T_{init} + n \log n)$ (and $\Omega(T_{init} \log T_{init})$ for $n=1$)
iterations without bloat control on MAJORITY.
