A veces, queremos decir que un algoritmo toma por lo menos una cierta cantidad de tiempo, sin dar una cota superior. Utilizamos la notación Ω grande; esa es la letra griega "omega".
Si un tiempo de ejecución es Ω(f(n)) \Omega(f(n)) , entonces para una n suficientemente grande, el tiempo de ejecución es por lo menos k, dot, f, left parenthesis, n, right parenthesis para alguna constante k. Aquí está cómo pensar acerca de un tiempo de ejecución que es Ω(f(n)) \Omega(f(n)) :
6n^2 vs 100n+300
Decimos que el tiempo de ejecución es "Ω grande de f, left parenthesis, n, right parenthesis". Usamos la notación Ω grande para límites asintóticos inferiores, ya que acota el crecimiento del tiempo de ejecución por abajo para entradas de tamaños suficientemente grandes.
Así como Θ(f(n)) \Theta(f(n)) automáticamente implica O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, también implica Ω(f(n)) \Omega(f(n)) . De modo que podemos decir que el peor tiempo de ejecución de la búsqueda binaria es Ω(lgn) \Omega(\lg n) . También podemos hacer afirmaciones correctas, pero imprecisas, al usar la notación Ω grande. Por ejemplo, así como si en verdad tuvieras un millón de pesos en el bolsillo, sinceramente puedes decir "tengo una cantidad de dinero en mi bolsillo, y es por lo menos 10 pesos", también puedes decir que el peor tiempo de ejecución de la búsqueda binaria es Ω(1) \Omega(1) , porque por lo menos toma un tiempo constante.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.