  Vector Addition Systems with States (VASS) provide a well-known and
fundamental model for the analysis of concurrent processes, parameterized
systems, and are also used as abstract models of programs in resource bound
analysis. In this paper we study the problem of obtaining asymptotic bounds on
the termination time of a given VASS. In particular, we focus on the
practically important case of obtaining polynomial bounds on termination time.
Our main contributions are as follows: First, we present a polynomial-time
algorithm for deciding whether a given VASS has a linear asymptotic complexity.
We also show that if the complexity of a VASS is not linear, it is at least
quadratic. Second, we classify VASS according to quantitative properties of
their cycles. We show that certain singularities in these properties are the
key reason for non-polynomial asymptotic complexity of VASS. In absence of
singularities, we show that the asymptotic complexity is always polynomial and
of the form $\Theta(n^k)$, for some integer $k\leq d$, where $d$ is the
dimension of the VASS. We present a polynomial-time algorithm computing the
optimal $k$. For general VASS, the same algorithm, which is based on a complete
technique for the construction of ranking functions in VASS, produces a valid
lower bound, i.e., a $k$ such that the termination complexity is $\Omega(n^k)$.
Our results are based on new insights into the geometry of VASS dynamics, which
hold the potential for further applicability to VASS analysis.
