Introduction to growth of functions

This learning module has many interactive demos. It is easier to work with them on a larger screen. Bookmark and revisit if you are currently on a small screen device.

\(\DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\asterisk}{\ast} \newcommand{\sup}{\text{sup}} \newcommand{\inf}{\text{inf}} \newcommand{\min}{\text{min}\;} \newcommand{\max}{\text{max}\;} \newcommand{\maxunder}[1]{\underset{#1}{\max}} \newcommand{\minunder}[1]{\underset{#1}{\min}} \newcommand{\real}{\mathbb{R}} \newcommand{\natural}{\mathbb{N}} \newcommand{\integer}{\mathbb{Z}} \newcommand{\rational}{\mathbb{Q}} \newcommand{\irrational}{\mathbb{I}} \newcommand{\complex}{\mathbb{C}} \newcommand{\cardinality}[1]{|#1|} \newcommand{\vec}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\mathbf{#1}} \newcommand{\star}[1]{#1^*} \newcommand{\inv}[1]{#1^{-1}} \newcommand{\indicator}[1]{\mathcal{I}(#1)} \renewcommand{\BigO}[1]{\mathcal{O}(#1)} \renewcommand{\BigOsymbol}{\mathcal{O}} \renewcommand{\smallo}[1]{\mathcal{o}(#1)} \renewcommand{\smallosymbol}[1]{\mathcal{o}} \newcommand{\set}[1]{\mathbb{#1}} \newcommand{\complement}[1]{#1^c} \newcommand{\powerset}[1]{\mathcal{P}(#1)} \newcommand{\setdiff}{\setminus} \newcommand{\setsymmdiff}{\oplus} \newcommand{\dash}[1]{#1^{'}} \newcommand{\permutation}[2]{{}_{#1} \mathrm{ P }_{#2}} \newcommand{\combination}[2]{{}_{#1} \mathrm{ C }_{#2}} \newcommand{\prob}[1]{P(#1)} \newcommand{\pmf}[1]{P(#1)} \newcommand{\pdf}[1]{p(#1)} \newcommand{\cdf}[1]{F(#1)} \newcommand{\expect}[2]{E_{#1}\left[#2\right]} \newcommand{\entropy}[1]{\mathcal{H}\left[#1\right]} \newcommand{\expe}[1]{\mathrm{e}^{#1}} \newcommand{\textexp}[1]{\text{exp}\left(#1\right)} \def\independent{\perp\!\!\!\perp} \def\notindependent{\not\!\independent} \newcommand{\yhat}{\hat{y}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vk}{\vec{k}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vmu}{\vec{\mu}} \newcommand{\vsigma}{\vec{\sigma}} \newcommand{\vphi}{\vec{\phi}} \newcommand{\vtau}{\vec{\tau}} \newcommand{\vtheta}{\vec{\theta}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mH}{\mat{H}} \newcommand{\mK}{\mat{K}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mI}{\mat{I}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mSigma}{\mat{\Sigma}} \newcommand{\mTheta}{\mat{\theta}} \newcommand{\setsymb}[1]{#1} \newcommand{\sA}{\setsymb{A}} \newcommand{\sB}{\setsymb{B}} \newcommand{\sC}{\setsymb{C}} \newcommand{\sO}{\setsymb{O}} \newcommand{\sP}{\setsymb{P}} \newcommand{\sQ}{\setsymb{Q}} \newcommand{\sH}{\setsymb{H}} \newcommand{\sX}{\setsymb{X}} \newcommand{\sY}{\setsymb{Y}} \newcommand{\norm}[2]{||{#1}||_{#2}} \newcommand{\infnorm}[1]{\norm{#1}{\infty}} \newcommand{\fillinblank}{\text{ }\underline{\text{ ? }}\text{ }} \newcommand{\lbrace}{\left\{} \newcommand{\rbrace}{\right\}} \newcommand{\set}[1]{\lbrace #1 \rbrace} \newcommand{\seq}[1]{\left( #1 \right)} \newcommand{\ndim}{N} \newcommand{\ndimsmall}{n} \newcommand{\dataset}{\mathbb{D}} \newcommand{\ndata}{D} \newcommand{\ndatasmall}{d} \newcommand{\labeledset}{\mathbb{L}} \newcommand{\nlabeled}{L} \newcommand{\nlabeledsmall}{l} \newcommand{\unlabeledset}{\mathbb{U}} \newcommand{\nunlabeled}{U} \newcommand{\nunlabeledsmall}{u} \newcommand{\nclass}{M} \newcommand{\nclasssmall}{m} \newcommand{\loss}{\mathcal{L}} \newcommand{\sign}{\text{sign}} \newcommand{\Gauss}{\mathcal{N}} \newcommand{\hadamard}{\circ} \newcommand{\doh}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\dox}[1]{\doh{#1}{x}} \newcommand{\doy}[1]{\doh{#1}{y}} \newcommand{\doxx}[1]{\doh{#1}{x^2}} \newcommand{\doyy}[1]{\doh{#1}{y^2}} \newcommand{\doxy}[1]{\frac{\partial #1}{\partial x \partial y}} \newcommand{\doyx}[1]{\frac{\partial #1}{\partial y \partial x}} \newcommand{\qed}{\tag*{$\blacksquare$}}\)

        Growth of functions
        Foundations of mathematics
      

Introduction

Understanding the growth of functions is essential to learning concepts such as computational complexity (in the case of algorithms) and convergence (in the case of random variables). In this article, we introduce the tools and notation to estimate and represent the relative rates of growths of functions.

Asymptotic tight bounds

Let us describe a set of functions of the variable $ n $ that grow similar to the function $ g(n) $ up to some constant factors when $ n \ge n_0 $. Say $ f(n) $ is one such function. For $ f(n) $ to grow equally as $ g(n) $ upto some constant factor, it should be the case that there exist some positive constants $ c_1 $ and $ c_2 $ for all $ n \ge n_0 $,

$$ 0 \le c_1 f(n) \le g(n) \le c_2 f(n) $$.

The following figure shows an example of such a function. Notice how the function $f(n)$ stays bounded within the confines of constant factors of $ g(n) $.

There could be many functions that are within such constant factors of the function $ g(n) $ for all $ n \ge n_0 $. We call the set of such functions $ \Theta(g(n)) $. We describe the relationship that $ f(n) $ is contained within such as a set as $ f(n) = \Theta(g(n)) $. We say that $g(n)$ is an asymptotically tight bound for $f(n) $.

The $ \theta $-notation

$$ 0 \le c_1 f(n) \le g(n) \le c_2 f(n) $$.

The following figure shows an example of such a function. Notice how the function $f(n)$ stays bounded within the confines of constant factors of $ g(n) $.

There could be many functions that are within such constant factors of the function $ g(n) $ for all $ n \ge n_0 $. We call the set of such functions $ \theta(g(n)) $. We describe the relationship that $ f(n) $ is contained within such as a set as $ f(n) = \theta(g(n)) $. We say that $g(n)$ is an asymptotically tight bound for $f(n) $.

The $ \BigOsymbol $-notation

The $ \theta $-notation is useful when we can find a function $ g(n) $ that upper bounds as well as lower bounds the function $ f(n) $ up to a constant factor for all values of $ n \ge n_0 $.

Sometimes, we can only upper bound. That means there exists some positive constant $ c $ such that for all $ n \ge n_0 $,

$$ 0 \le f(n) \le c g(n) $$

We call such a function an asymptotic upper bound. We describe the relationship as $ f(n) = \BigO{g(n)} $.

Note that if a function can be upper as well as lower bounded by $g(n)$, then it is still in $ \BigO{g(n)} $. This means

$$ f(n) = \theta(g(n)) \Rightarrow f(n) = \BigO{g(n)} $$

$ \theta $ is a symmetric relation

Suppose $ f(n) = \theta(g(n)) $. This means, there exist some positive constants $ c_1 $ and $ c_2 $ such that for some values of $ n \ge n_0 $,

$$ 0 \le c_1 g(n) \le f(n) \le c_2 g(n) $$

Note that if $ c_1 g(n) \le f(n) $, then $ g(n) \le \frac{1}{c_1} f(n) $. Similarly, $ f(n) \le c_2 g(n) $ means that $ \frac{1}{c_2} f(n) \le g(n) $. These two equations can be written as

$$ 0 \le \frac{1}{c_2} f(n) \le g(n) \le \frac{1}{c_1} f(n) $$

Thus, the function $ g(n) = \theta(f(n)) $. Thus, the asymptotic relation $ \theta $ is symmetric. This means,

$$ f(n) = \theta(f(n)) \text{ if and only if } g(n) = \theta(f(n)) $$

Transitivity of asymptotic bounds

Suppose $ f(n) = \BigO{g(n)} $. This means, there exist some positive constant $ c $ such that for some values of $ n \ge n_0 $,

$$ 0 \le f(n) \le c g(n) $$

Now suppose there is another function $ h(n) $ that upper bounds $ g(n) $. This means, $ g(n) = \BigO{h(n)} $. By definition, it implies that there is some positive constant $ d $, such that

$$ 0 \le g(n) \le d h(n) $$

Collectively, the two inequalities imply that

$$ 0 \le f(n) \le cd h(n) $$

Thus, it is the case tha t$ f(n) = \BigO{h(n)} $.

This means,

$$ f(n) = \BigO{g(n)} \text{ and } g(n) = \BigO{h(n)} \text{ imply } f(n) = \BigO{h(n)} $$

Similar transitive can be derived for the other asymptotic bounds. We list them here.

$$ f(n) = \Omega(g(n)) \text{ and } g(n) = \Omega(h(n)) \text{ imply } f(n) = \Omega(h(n)) $$ $$ f(n) = \theta(g(n)) \text{ and } g(n) = \theta(h(n)) \text{ imply } f(n) = \theta(h(n)) $$ $$ f(n) = \smallo{g(n)} \text{ and } g(n) = \smallo{h(n)} \text{ imply } f(n) = \smallo{h(n)} $$ $$ f(n) = \omega(g(n)) \text{ and } g(n) = \omega(h(n)) \text{ imply } f(n) = \omega(h(n)) $$

Next-article

Study our other mathematical articles for a strong foundation to tackle advanced material.

Please support us

Help us create more engaging and effective content and keep it free of paywalls and advertisements!

Please donate

Let's connect

Please share your comments, questions, encouragement, and feedback.

Growth of functions

Foundations of mathematics

Introduction

Asymptotic tight bounds

The \( \theta \)-notation

The \( \BigOsymbol \)-notation

\( \theta \) is a symmetric relation

Transitivity of asymptotic bounds

Next-article

Please support us

Let's connect