A menudo es más fácil verificar una solución correcta a un problema que producir la solución en primer lugar. El desafío P versus NP, la más importante de las preguntas matemáticas abiertas, pregunta si todos los problemas que una computadora puede verificar de manera eficiente también pueden resolverse de manera eficiente.
Para hacer una analogía, imagine que está armando un rompecabezas de una imagen sin rasgos distintivos, como una imagen de cielo azul claro. Probar todas las combinaciones posibles de piezas para ver si encajan es difícil; decir que llevaría mucho tiempo es un eufemismo. Sin embargo, una vez que se completa el rompecabezas, es fácil verificar que se haya hecho correctamente. Las definiciones más rigurosas de lo que significa eficiencia se expresan matemáticamente en términos de qué tan rápido funciona el algoritmo a medida que el problema se vuelve más complicado, cuando se agregan más piezas al rompecabezas. El conjunto de problemas que se pueden resolver rápidamente (en lo que se conoce como tiempo polinomial) se llama P. Un grupo más grande de problemas que se pueden verificar rápidamente, pero no necesariamente se resuelven rápidamente, se conoce como NP (que significa tiempo polinomial no determinista) ) Los problemas P son un subconjunto de problemas NP, ya que al resolver el problema rápidamente, hemos verificado automáticamente la solución que encontramos.
Con cinco registros para ordenar, tuvimos que rastrear cuatro veces la lista sin clasificar, haciendo cuatro comparaciones cada vez. Con diez registros tendríamos que realizar nueve pases, con nueve comparaciones cada vez. Esto significa que la cantidad de trabajo que tenemos que hacer durante la ordenación crece casi como el cuadrado del número de objetos que estamos ordenando. Si tiene una gran colección, entonces esto sigue siendo mucho trabajo, pero treinta registros tomarían cientos de comparaciones en lugar de billones y billones de permutaciones posibles que podríamos tener que verificar con un algoritmo de fuerza bruta que enumera todas las órdenes posibles. A pesar de esta gran mejora, los expertos en informática suelen considerar que el tipo de burbuja es ineficiente. En aplicaciones prácticas, como el feed de noticias de Facebook o el feed de fotos de Instagram, donde miles de millones de publicaciones deben clasificarse y mostrarse de acuerdo con las últimas prioridades de los gigantes tecnológicos, se evitan los tipos de burbujas simples en favor de primos más recientes y más eficientes. El «tipo de fusión», por ejemplo, divide las publicaciones en pequeños grupos, que luego clasifica rápidamente y combina en el orden correcto.