Re: [obm-l] (O (sqrt n))

["Domingos Jr." <dopikas@xxxxxxxxxx>]

> Quando eu mando o Maple fazer uma série de Taylor para uma função, aparece
> esse O também.
> Creio eu que seja algo muito pequeno, um infinitesimal, não sei direito.
>
> Henrique.


Não necessariamente, a notação O na verdade significa:

f(x) = O(g(x)) => existe uma constante c que, para todo x > x0, temos f(x) <
c.g(x).
se estivermos valando de valores pequenos basta trocar o x > x0 por x < x0
na definição e está resolvido.

Na verdade o igual do "f(x) = O(g(x))" é um abuso de notação, pois O(g(x)) é
o conjunto de todas as funções que limitam superiormente g(x) da forma
definida acima, sendo assim a notação formal seria f(x) pertence a O(g(x)),
mas o igual acabou permanecendo e resiste até hoje.

Em análise de algoritmos essa notação é bastante usada para se dar uma idéia
de como o algoritmo se comporta no pior caso de uma entrada de dados, por
exemplo, multiplicação de 2 matrizes densas n x n feita da maneira
tradicional é O(n³).

[ ]'s

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================