computer science

Quasi-polynomial growth

Quasi-polynomial growth is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Quasi-polynomial growth rather than just read about it. In short: In theoretical computer science, a function f ( n ) {\displaystyle f(n)} is said to exhibit quasi-polynomial growth when it has an upper bound of the form f ( n ) = 2 O ( ( log ⁡ n ) c ) {\displaystyle f(n)=2^{O{\bigl (}(\log n)^{c}{\bigr )}}} for some constant c {\displaystyle c} , as expressed using big O notation. That is, it is bounded by an exponential function of a polylogarithmic function.

Key takeaways

Quasi-polynomial growth belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Quasi-polynomial growth to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Quasi-polynomial growth from memory before moving on to harder problems.

Reference excerpt

In theoretical computer science, a function f ( n ) {\displaystyle f(n)} is said to exhibit quasi-polynomial growth when it has an upper bound of the form

f ( n ) = 2 O ( ( log ⁡ n ) c ) {\displaystyle f(n)=2^{O{\bigl (}(\log n)^{c}{\bigr )}}}

for some constant c {\displaystyle c} , as expressed using big O notation. That is, it is bounded by an exponential function of a polylogarithmic function. This generalizes the polynomials and the functions of polynomial growth, for which one can take c = 1 {\displaystyle c=1} . A function with quasi-polynomial growth is also said to be quasi-polynomially bounded. 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. In particular, algorithms whose worst-case running times exhibit quasi-polynomial growth are said to take quasi-polynomial time. As well as time complexity, some algorithms require quasi-polynomial space complexity, use a quasi-polynomial number of parallel processors, can be expressed as algebraic formulas of quasi-polynomial size or have a quasi-polynomial competitive ratio. 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. 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. 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, or relating the sizes of cliques and independent sets in certain classes of graphs. 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.

References

Worked examples

Example 1 — a first encounter with Quasi-polynomial growth

Start with the simplest possible case. Write down what Quasi-polynomial growth claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Quasi-polynomial growth before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Quasi-polynomial growth ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Quasi-polynomial growth

In research: Quasi-polynomial growth appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Quasi-polynomial growth in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Quasi-polynomial growth is common in secondary-school and first-year university syllabi. It links to neighbouring topics Asymptotic analysis, Computational complexity theory, so understanding it makes those chapters shorter.
In everyday life: Look for Quasi-polynomial growth outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Quasi-polynomial growth” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Quasi-polynomial growth in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Quasi-polynomial growth means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Quasi-polynomial growth out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Quasi-polynomial growth in simple terms?

In theoretical computer science, a function f ( n ) {\displaystyle f(n)} is said to exhibit quasi-polynomial growth when it has an upper bound of the form f ( n ) = 2 O ( ( log ⁡ n ) c ) {\displaystyle f(n)=2^{O{\bigl (}(\log n)^{c}{\bigr )}}} for some constant c {\displaystyle c} , as expressed us…

Why does Quasi-polynomial growth matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Quasi-polynomial growth?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Quasi-polynomial growth.