both in theoretical work and in practice, but our tools for estimating
their running times (e.g. O(c^n) for some c) are still somewhat
primitive.
One major step here is the work by David Eppstein on modelling the
execution of an algorithm through the use of multi-variate
recurrences. Within the bounds of such a model, a so-called complexity
measure which is asymptotically tight can be calculated automatically
(although the tightness does of course not extend beyond the model of
the algorithm). This work is presented.
Extensions to the model from our own work are also shown, relaxing
a certain uniformity assumption in Eppstein's work to model the
execution of the algorithm better. Under these models, the automatic
calculation of some upper bound is still possible, but very few
results of tightness of these bounds with respect to the model are
known.