La notación O grande es una notación matemática que describe el comportamiento limitante de una función cuando el argumento tiende hacia un valor particular o infinito. Es miembro de una familia de notaciones inventadas por Paul Bachmann ,  Edmund Landau , y otros, denominados colectivamente notación de Bachmann-Landau o notación asintótica .

En ciencias de la computación, la notación O grande se usa para clasificar los algoritmos de acuerdo con cómo crecen sus requisitos de tiempo de ejecución o espacio a medida que aumenta el tamaño de entrada. En la teoría de números analíticos , la notación O grande se usa a menudo para expresar un límite en la diferencia entre una función aritmética y una aproximación mejor entendida; Un ejemplo famoso de tal diferencia es el término restante en el teorema del número primo .

La notación O grande caracteriza las funciones de acuerdo con sus tasas de crecimiento: diferentes funciones con la misma tasa de crecimiento pueden representarse usando la misma notación O.

La letra O se usa porque la tasa de crecimiento de una función también se conoce como el orden de la función . Una descripción de una función en términos de notación O grande generalmente solo proporciona un límite superior en la tasa de crecimiento de la función. Asociadas con la notación O grande hay varias notaciones relacionadas, usando los símbolos o , Ω, ω y Θ , para describir otros tipos de límites en las tasas de crecimiento asintótico.

Big O

La notación O, afirma que existe un punto N0 tal que para todos los valores de Ndespués de este punto,  T(N) está acotada por algún múltiplo de F(N). Con el N lo suficientemente grande.

Por lo tanto, si el tiempo de ejecución T(N) de un algoritmo es de O(N²), entonces ignorando las constantes, podemos garantizar que a partir de un punto se puede acotar el tiempo de ejecución mediante una función cuadrática.

Ejemplo: Consideremos el algoritmo de búsqueda secuencial para encontrar un valor especificado en un arreglo. Si el visitar y comparar contra un valor en el arreglo, requiere CS pasos, entonces en el caso promedio . Para todos  los valores n>1 |cs n/2| ≤ cs|n|. Por lo tanto, por definición, T(n) está en O(n) para n0=1, y c=CS.

• Se adopta una notación especial llamada O-grande (big-O), por ejemplo O(f(n)) para indicar que la cota superior del algoritmo es f(n).

• En términos precisos, si T(n) representa el tiempo de ejecución de un algoritmo, y f(n) es alguna expresión para su cota superior, T(n) está en el conjunto O(f(n)), si existen dos constantes positivas C y n0  tales que  T(n) ≤ c|f(m)| para todo n≥n0.

• El sólo saber que algo es O(f(n)), sólo nos dice que tan mal se pueden poner las cosas. Quizás la situación no es tan mala. De la definición podemos ver que si T(n) está en O(n), también está en O(n2) y O(n3), etc. (Por lo cual se trata en general de definir la mínima cota superior).

Decir que f(n) es de orden O(g(n)), significa: