# Cota superior asimptòtica

En anàlisi d'algorismes una cota superior asimptòtica és una funció que serveix de cota superior d'una altra funció quan l'argument tendeix a infinit. Usualment s'utilitza la notació de Landau: O(g(x)), per referir-se a les funcions acotades superiorment per la funció g(x). Més formalment es defineix:
$O(g(x))=\left\{{\begin{matrix}f(x):{\mbox{existeixen }}x_{0},c>0{\mbox{ tals que}}\\\forall x\geq x_{0}>0:0\leq |f(x)|\leq c|g(x)|\end{matrix}}\right\}$
Una funció f(x) pertany a O(g(x)) quan hi ha una constant positiva c tal que a partir d'un valor $x_{0}$, $f(x)$ no supera cg(x). Vol dir que la funció f és inferior a g a partir d'un valor donat excepte per un factor constant.
La cota superior asimptòtica té utilitat en Teoria de la complexitat computacional quan es defininen les classes de complexitat.
Tot i que O(g(x)) està definit com un conjunt, s'acostuma a escriure f(x)= O(g(x)) en lloc de f(x)∈ O(g(x)). Moltes vegades també es parla d'una funció nomenant únicament la seva expressió, com en x² en lloc de h(x)=x², sempre que estigui clar quin és el paràmetre de la funció dins de l'expressió. En la gràfica es dona un exemple esquemàtic de com es comporta $cg(x)$ pel que fa a f(x) quan x tendeix a infinit. Cal notar a més que aquest conjunt és no buit doncs g(x)=O(g(x)).
La cota ajustada asimptòtica (notació Θ) té relació amb les cotes asimptòtiques superior (notació O) i inferior:
$f(x)=\Theta (g(x)){\mbox{ si i només si }}f(x)=O(g(x)){\mbox{ i }}f(x)=\Omega (g(x))$

## Propietats

Sigui $E\subseteq \mathbb {R}$, siguin $f_{1}:E\to \mathbb {R}$, $g_{1}:E\to \mathbb {R}$, $f_{2}:E\to \mathbb {R}$, $g_{2}:E\to \mathbb {R}$ funcions i $k$ un real. És compleixen els següents enunciats:
    i) Si $f_{1}=O(g_{1})\,$ y $g_{1}=O(g_{2})\,$, llavors $f_{1}=O(g_{2})\,$
    ii) Si $f_{1}=O(g_{1})\,$ y $f_{2}=O(g_{2})\,$, llavors $f_{1}f_{2}=O(g_{1}g_{2})\,$
    iii) $f_{2}O(g_{1})=O(f_{2}g_{1})\,$ (igualtat entre conjunts)
    iv) Si $f_{1}=O(g_{1})\,$ y $f_{2}=O(g_{2})\,$, llavors $f_{1}+f_{2}=O(|g_{1}|+|g_{2}|)\,$
    v) Si $k\neq 0\,$ llavors $O(g_{1})=O(kg_{1})\,$ (igualtat entre conjunts)
    vi) Si $f_{1}=O(g_{1})\,$, llavors $kf_{1}=O(g_{1})\,$.

## Exemples

* La funció f(x) = x + 10 pot ser fitada superiorment per la funció g(x) = x². Per demostrar-ho és prou notar que per a tot valor de x≥3.7016 es compleix x+10 ≤ x². Per tant, x+10 = O(x²). Però x² no serveix com a cota inferior per x+10, és a dir $x^{2}\neq \bigcirc (x+10)$.
* La funció 200x està fitada superiorment per x². Vol dir que quan x tendeix a infinit el valor de 200x es pot menysprear comparat amb el de x².

## Ordres usuals per a funcions

Els ordres més utilitzats en anàlisi d'algorismes, en ordre creixent, són els següents (on c representa una constant i n la mida de l'entrada):
| notació | nom |
| O(1) | ordre constant |
| O(log log n) | ordre sublogarítmic |
| O(log n) | ordre logarítmic |
| O(${\sqrt {n}}$) | ordre sublineal |
| O(n) | ordre lineal o de primer ordre |
| O(n · log n) | ordre lineal logarítmic |
| O(n²) | ordre quadràtic o de segon ordre |
| O(n$^3$), ... | ordre cúbic o de tercer ordre, ... |
| O(n$^c$) | ordre potencial fix |
| O(c$^n$), n > 1 | ordre exponencial |
| O(n!) | ordre factorial |
| O(n$^n$) | ordre potencial exponencial |

## Vegeu també

* Cota inferior asimptòtica
* Cota superior asimptòtica
* Notació de Landau

## Bibliografia

* Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein