[Abeja]

  Hola

  Qué significa que la eficiencia de un método de ordenamiento sea de \( \mathcal O(n^2) \) ? Método de inserción por ejemplo.

  Ojalá alguien se maneje en el tema para que me ayude. 

[Luis Fuentes]

Hola

 Quiere decir que el tiempo \( T(n) \) que se tarda en ordenar \( n \) datos con ese algoritmo es:

 existen constantes \( c>0 \) y \( n_0 \) tales que \( T(n)\leq cn^2 \) para \( n\geq n_0 \)

 De manera intutiva estamos diciendo que si multiplicamos por \( k \) el volumen de datos, el tiempo de ordenación de multiplica por \( k^2 \). Eso nos da una idea de la velocidad del algoritmo y de como se "lentifica" al aumentar el volumen de datos.

 Puedes leer una introducción aquí:

http://web.jet.es/jqc/progii2.html

 y algo más formal aquí:

http://decsai.ugr.es/~jhg/TA/PresentacionEficiencia.pdf

Saludos.