  We suggest that straight-line programs designed for algebraic computations
should be accompanied by a comprehensive complexity analysis that takes into
account both the number of fundamental algebraic operations needed, as well as
memory requirements arising during evaluation. We introduce an approach for
formalising this idea and, as illustration, construct and analyse straight-line
programs for the Bruhat decomposition of $d\times d$ matrices with determinant
$1$ over a finite field of order $q$ that have length $O(d^2\log(q))$ and
require storing only $O(\log(q))$ matrices during evaluation.
