Notació asimptòtica

La notació asimptòtica és una eina matemàtica que permet expressar l'eficiència dels algorismes de manera senzilla i clara. Però per un moment, oblidem-nos dels algorismes, i centrem-nos en les matemàtiques. A continuació es presenten les principals notacions asimptòtiques que necessitem i es presenten les seves propietats bàsiques. També s'inclouen exemples d'ús i es donen exemples i intuïcions per entendre-les millor.

Notació O gran

Definició: Donada una funció $g:\mathbb{N}\to \mathbb{N}$, es defineix la notació O gran com:

$$O(g)=\{f:\mathbb{N}\to \mathbb{N}\mid \mathrm{\exists }c\in \mathbb{N}:\mathrm{\exists }{n}_0\in \mathbb{N}:\mathrm{\forall }n\ge n_0:f(n)\le c\cdot g(n)\}$$

Així doncs, $O(g)$ és el conjunt de les funcions que creixen com a màxim tan ràpidament com $g$ per a valors grans de $n$, ignorant constants multiplicatives i termes d'ordre menor.

Exemple: Si $f(n)=3n^2+100n+5$, llavors $f(n)\in O(n^2)$.

Demostració: Cal trobar constants $c$ i $n_0$ tals que per a tot $n\ge n_0$, es compleixi que $f(n)\le c\cdot n^2$. En aquest cas, podem triar $c=4$ i $n_0=101$. En efecte, per a $n\ge 101$, tenim que $4n^2\ge 3n^2+100n+5$. ▢

Visualització de O gran

TODO: Fer una gràfica.

Exemples i intuïcions per a O gran

A continuació es dónen uns exemples de l'ús de la notació O gran:

• $3n^2+5n-7\in O(n^3)$
• $n+15\in O(n)$
• $O(n^5)\subseteq O(n^6)$
• $n^3\notin O(n^2)$
• $n^3\in O(2^n)$

Intuitivament, podem entendre aquesta notació de la següent manera:

• $f(n)\in O(g(n))$ significa que, per a valors grans de $n$, la funció $f(n)$ creix com a màxim, tan ràpidament com $g(n)$, tot ignorant la seva pendent i què passa per a valors petits de $n$.

Notacions Omega i Theta

Un cop presentada la O gran, introduïm dues notacions complementàries que ens permeten caracteritzar millor el creixement de les funcions.

Definicions: Donada una funció $g:\mathbb{N}\to \mathbb{N}$, es defineixen:

$$\mathrm{\Omega }(g)=\{f:\mathbb{N}\to \mathbb{N}\mid \mathrm{\exists }c\in \mathbb{N}:\mathrm{\exists }{n}_0\in \mathbb{N}:\mathrm{\forall }n\ge n_0:f(n)\ge c\cdot g(n)\}$$$$\mathrm{\Theta }(g)=\{f:\mathbb{N}\to \mathbb{N}\mid \mathrm{\exists }{c}_1,c_2\in \mathbb{N}:\mathrm{\exists }{n}_0\in \mathbb{N}:\mathrm{\forall }n\ge n_0:c_{1}g(n)\le f(n)\le c_{2}g(n)\}$$

Així doncs:

• $\mathrm{\Omega }(g)$ és el conjunt de les funcions que creixen com a mínim tan ràpidament com $g$ per a valors grans de $n$, ignorant constants multiplicatives i termes d'ordre menor.

• $\mathrm{\Theta }(g)$ és el conjunt de les funcions que creixen exactament com $g$ per a valors grans de $n$, ignorant constants multiplicatives i termes d'ordre menor.

Seguint amb l'exemple anterior, si $f(n)=3n^2+100n+5$, es pot comprovar que $f(n)\in \mathrm{\Omega }(n^2)$ i, per tant, $f(n)\in \mathrm{\Theta }(n^2)$.

Exemples i intuïcions per a Omega i Theta

Aquests són uns exemples de l'ús de la notació $\mathrm{\Omega }$:

• $2^n\in \mathrm{\Omega }(n)$
• $n^2\in \mathrm{\Omega }(n)$
• $n\in \mathrm{\Omega }(n)$
• $n\notin \mathrm{\Omega }(n^2)$
• $\mathrm{\Omega }(n^6)\subseteq \mathrm{\Omega }(n^5)$

I ara uns exemples de l'ús de la notació $\mathrm{\Theta }$:

• $75n\in \mathrm{\Theta }(n)$
• $1023n^2\notin \mathrm{\Theta }(n)$
• $n^2\notin \mathrm{\Theta }(n)$
• $2^n\notin \mathrm{\Theta }(2^{n^2})$
• $\mathrm{\Theta }(n)\ne \mathrm{\Theta }(n^2)$

Convencions

Malgrat que $O(g)$ és un conjunt de funcions i no una funció en si mateixa, sovint es comet un abús de notació i s'utilitza la notació $f(n)=O(g(n))$ per indicar que $f\in O(g)$.

Aquesta és una convenció àmpliament utilitzada en l'anàlisi d'algorismes i facilita la comunicació dels resultats. Per tant, no ens n'estarem d'utilitzar-la. Però sempre cal tenir present que, estrictament parlant, $O(g)$ és un conjunt de funcions i no una funció en si mateixa.

Amb aquest convenció, escriurem expressions com ara

$$3(n-1)(n+2)=3n^2+3n-6=O(n^2)=O(n^3)$$

que, en realitat, vol dir que

$$3(n-1)(n+2)=3n^2+3n-6\in O(n^2)\subset O(n^3).$$

Igualment, és habitual estendre la notació a altres dominis diferents de $\mathbb{N}$, com ara ${\mathbb{R}}^{+}$, això no comporta cap problema.

Propietats

Donades dues funcions $f$ i $g$, aquestes propietats relacionen les diferents notacions asimptòtiques:

• $f=\mathrm{\Omega }(g)⟺g=O(f)$
• $\mathrm{\Theta }(f)=O(f)\cap \mathrm{\Omega }(f)$
• $f=\mathrm{\Theta }(g)⟺f=O(g)$ i $f=\mathrm{\Omega }(g)$

Donades les funcions $f$, $f_1$, $f_2$, $g$, $g_1$, $g_2$ i $h$, la O gran compleix les propietats següents:

• Reflexivitat: $f=O(f)$
• Transitivitat: $h=O(g)\wedge g=O(f)\Rightarrow h=O(f)$
• Caracterització: $g=O(f)⟺O(g)\subseteq O(f)$
• Suma: $g_1=O(f_1)\wedge g_2=O(f_2)\Rightarrow g_1+g_2=O(f_1+f_2)=O(max(f_1,f_2))$
• Producte: $g_1=O(f_1)\wedge g_2=O(f_2)\Rightarrow g_1\cdot g_2=O(f_1\cdot f_2)$
• Invariància multiplicativa: Per a tota constant $c={\mathbb{R}}^{+}$, $O(f)=O(c\cdot f)$

Per a $\mathrm{\Omega }$ es compleixen propietats similars, i en el cas de $\mathrm{\Theta }$ es compleixen les següents propietats:

• Reflexivitat: $f=\mathrm{\Theta }(f)$
• Transitivitat: $h=\mathrm{\Theta }(g)\wedge g=\mathrm{\Theta }(f)\Rightarrow h=\mathrm{\Theta }(f)$
• Simetria: $g=\mathrm{\Theta }(f)⟺f=\mathrm{\Theta }(g)⟺\mathrm{\Theta }(g)=\mathrm{\Theta }(f)$
• Suma: $g_1=\mathrm{\Theta }(f_1)\wedge g_2=\mathrm{\Theta }(f_2)\Rightarrow g_1+g_2=\mathrm{\Theta }(f_1+f_2)=\mathrm{\Theta }(max(f_1,f_2))$
• Producte: $g_1=\mathrm{\Theta }(f_1)\wedge g_2=\mathrm{\Theta }(f_2)\Rightarrow g_1\cdot g_2=\mathrm{\Theta }(f_1\cdot f_2)$
• Invariància multiplicativa: Per a tota constant $c={\mathbb{R}}^{+}$, $\mathrm{\Theta }(f)=\mathrm{\Theta }(c\cdot f)$

Més abusos de notació

Seguint amb l'abús de notació esmentat anteriorment, es solen usar directament operacions entre les classes de funcions definides per les notacions asimptòtiques:

Si ${\mathcal{F}}_1$ i ${\mathcal{F}}_2$ són classes de funcions (com ara $O(f)$ o $\mathrm{\Omega }(f)$):

• ${\mathcal{F}}_1+{\mathcal{F}}_2=\{f+g\mid f={\mathcal{F}}_1\wedge g={\mathcal{F}}_2\}$
• ${\mathcal{F}}_1\cdot {\mathcal{F}}_2=\{f\cdot g\mid f={\mathcal{F}}_1\wedge g={\mathcal{F}}_2\}$

En aquest context, es compleixen les propietats següents per a dues funcions $f$ i $g$ qualssevol:

• $O(f)+O(g)=O(f+g)=O(max\{f,g\})$
• $O(f)\cdot O(g)=O(f\cdot g)$
• $\mathrm{\Theta }(f)+\mathrm{\Theta }(g)=\mathrm{\Theta }(f+g)=\mathrm{\Theta }(max\{f,g\})$
• $\mathrm{\Theta }(f)\cdot \mathrm{\Theta }(g)=\mathrm{\Theta }(f\cdot g)$

Exercicis

Compara asimptòticament les següents parelles de funcions i indica quina creix més ràpidament quan $n$ tendeix a l'infinit:

• $n^{412}$ vs ${1.02}^n$
• $243n^2$ vs $n^3$
• $2^n$ vs $3^n$
• $(\log n{)}^{923}$ vs $n^{0.0001}$
• $n(\ln n{)}^4$ vs $n^2\ln n$
• $({\log }_{2}7{)}^n$ vs $({\log }_{4}7{)}^n$
• $(\ln n{)}^{7842}$ vs ${1.001}^n$
• $n{2}^n$ vs $n^3{1.5}^n$
• $2^{\sqrt{\log n}}$ vs $n$

Jordi Petit
Lliçons.jutge.org
© Universitat Politècnica de Catalunya, 2025