Grande-O

Na matemática, a notação O-grande descreve o comportamento limitante de uma função quando o argumento tende a um valor específico ou para o infinito, normalmente, em termos de funções mais simples. É membro de uma família maior de notações conhecida como notação Landau, notação Bachmann–Landau (nomeada dessa forma por conta de Edmund Landau e Paul Bachmann), ou notação assintótica. Em ciência da computação, o O-grande é usado para classificar algoritmos pela forma como eles respondem (ex., no tempo de processamento ou espaço de trabalho requerido) a mudanças no tamanho da entrada. Na teoria analítica dos números, é usado para estimar o "erro cometido" quando se substitui o tamanho assintótico, ou o tamanho assintótico médio, de uma função aritmética, pelo valor, ou pelo valor médio, que ela recebe num argumento grande e finito. Um exemplo famoso é o problema de estimar o termo restante no teorema do número primo. A notação O-grande caracteriza funções de acordo com suas taxas de crescimento: funções diferentes com as mesmas taxas de crescimento têm a mesma notação O-grande. A letra O é usada porque a taxa de crescimento de uma função também é referenciada como a ordem de uma função. Uma descrição de uma função em termos de O-grande normalmente provê um limite superior na taxa de crescimento da função. Associada a notação O-grande existem várias outras notações, usando os símbolos o, Ω, ω, e Θ, para descrever outros tipos de relacionamento com taxas de crescimento assintóticas. A notação O-grande é também usada por muitos campos para prover estimativas similares.