Notação Big O

---

A notação Big O, ou $O(g(n))$, é utilizada na análise de algoritmos para descrever um limite superior do crescimento de uma função à medida que o tamanho da entrada $n$ aumenta. Ela nos dá uma forma de quantificar como a complexidade de um algoritmo escala com o tamanho do problema, concentrando-se na taxa de crescimento da função no pior caso.

Definição Formal

Para uma função $g(n)$, o conjunto de funções $O(g(n))$ é definido como:

$$O(g(n))=\{f(n):\exists c>0\text{ e }{n}_0>0\text{ tal que }f(n)\le c\cdot g(n),\forall n\ge n_0\}$$

Isso significa que, após um determinado valor $n_0$, a função $f(n)$ nunca cresce mais rápido que uma constante multiplicada por $g(n)$. Ou seja, $g(n)$ delimita o crescimento de $f(n)$ de forma assintótica.

Interpretação

A notação $O(g(n))$ é usada para atribuir um limite superior para a função de complexidade. Em termos simples, se uma função $f(n)$ está em $O(g(n))$, isso quer dizer que, para entradas grandes o suficiente, $f(n)$ não cresce mais rápido que $g(n)$, até uma constante multiplicativa.

Exemplo 1: Verificar se $2n+10=O(n)$

Aplicando a definição, queremos verificar se existe uma constante $c$ tal que:

$$2n+10\le c\cdot n\forall n\ge n_0$$

Podemos reorganizar:

$$2n+10\le 12n$$

Tomando $c=12$ e $n_0=1$, a desigualdade é verdadeira. Logo, podemos dizer que $2n+10=O(n)$, o que significa que, para valores grandes de $n$, a função $2n+10$ cresce linearmente, assim como $n$.

Exemplo 2: Verificar se $n^2=O(n)$

Agora, queremos verificar se $n^2\le c\cdot n$ para algum $c>0$. Isso implicaria que:

$$n\le c$$

No entanto, isso não é possível, pois $n$ cresce indefinidamente enquanto $c$ é uma constante. Portanto, $n^2\ne O(n)$, ou seja, $n^2$ cresce mais rápido que $n$.

Referências

---

Aula 2 - Análise de algoritmos