  We investigate expansions of Presburger arithmetic, i.e., the theory of the
integers with addition and order, with additional structure related to
exponentiation: either a function that takes a number to the power of $2$, or a
predicate for the powers of $2$. The latter theory, denoted
$\mathrm{PresPower}$, was introduced by B\"uchi as a first attempt at
characterising the sets of tuples of numbers that can be expressed using finite
automata; B\"uchi's method does not give an elementary upper bound, and the
complexity of this theory has been open. The former theory, denoted as
$\mathrm{PresExp}$, was shown decidable by Semenov; while the decision
procedure for this theory differs radically from the automata-based method
proposed by B\"uchi, the method is also non-elementary. And in fact, the theory
with the power function has a non-elementary lower bound. In this paper, we
show that while Semenov's and B\"uchi's approaches yield non-elementary
blow-ups for $\mathrm{PresPower}$, the theory is in fact decidable in triply
exponential time, similar to the best known quantifier-elimination algorithm
for Presburger arithmetic. We also provide a $\mathrm{NExpTime}$ upper bound
for the existential fragment of $\mathrm{PresExp}$, a step towards a
finer-grained analysis of its complexity. Both these results are established by
analysing a single parameterized satisfiability algorithm for
$\mathrm{PresExp}$, which can be specialized to either the setting of
$\mathrm{PresPower}$ or the existential theory of $\mathrm{PresExp}$. Besides
the new upper bounds for the existential theory of $\mathrm{PresExp}$ and
$\mathrm{PresPower}$, we believe our algorithm provides new intuition for the
decidability of these theories, and for the features that lead to
non-elementary blow-ups.
