a repository of mathematical know-how

Which techniques lead to which kinds of bounds?

Quick description

How can a proof ever give a strange-looking bound like n\exp(-c\sqrt{\log n})? This is a good question, and getting to know the answer to it for this and other bounds is an important part of the know-how of mathematicians who deal with estimates. Here are links to articles that discuss how various different functions can occur as the end results of proofs. This article is closely related to an article about what a lower bound can say about potential proofs of the upper bound.

Kinds of bounds

Linear bounds

Quadratic bounds and square roots

Why do power-type bounds arise?

Exponential and logarithmic bounds

n\log n-type bounds

Double exponential and loglog bounds

Extra logarithmic factors

\exp(c\sqrt{\log n})-type bounds

Tower-type bounds

Ackermann-type bounds


Post new comment

(Note: commenting is not possible on this snapshot.)

Before posting from this form, please consider whether it would be more appropriate to make an inline comment using the Turn commenting on link near the bottom of the window. (Simply click the link, move the cursor over the article, and click on the piece of text on which you want to comment.)