is said to exhibit quasi-polynomial growth when it has an upper bound of the form
[1] Quasi-polynomial growth has been used in the analysis of algorithms to describe certain algorithms whose computational complexity is not polynomial, but is substantially smaller than exponential.
[5] In some other cases, quasi-polynomial growth is used to model restrictions on the inputs to a problem that, when present, lead to good performance from algorithms on those inputs.
[1] It can also bound the size of the output for some problems; for instance, for the shortest path problem with linearly varying edge weights, the number of distinct solutions can be quasipolynomial.
[6][7] Beyond theoretical computer science, quasi-polynomial growth bounds have also been used in mathematics, for instance in partial results on the Hirsch conjecture for the diameter of polytopes in polyhedral combinatorics,[8] or relating the sizes of cliques and independent sets in certain classes of graphs.
[9] However, in polyhedral combinatorics and enumerative combinatorics, a different meaning of the same word also is used, for the quasi-polynomials, functions that generalize polynomials by having periodic coefficients.