Notacion big O

version en video:

 

La notación de big o es una forma de medir y comparar el tiempo de ejecución de algoritmos.
Esta notación se puede usar para comparar dos implementaciones de algoritmos y posiblemente escoger la implementación más rápida.
hay que ser cuidadoso con esto en proyectos más halla de ejercisios por que para mi sigue siendo más prioritario hacer un código más mantenible y fácil de entender que un código que sea más rápido o teóricamente mas rapido(en mi caso por ejemplo me gusta mucho la programación funcional y la inmutabilidad para entender el código como bloques funcionales que reciben una entrada y retornan la misma salida para misma entrada, otro tema).
con esta aclaración igual creo que en el libro cracking the coding interview de gayle dan un ejemplo analogía muy bueno para entender el impacto de big o. Imaginemos que tenemos que transferir un archivo a un amigo y tenemos dos opciones.
transferir el archivo por internet(mandándolo por ejemplo por un correo electrónico).
llevar el archivo físico en un avión(por ejemplo en un disco duro)

en el primer caso transfiriendo el archivo por internet, entre mas grande el archivo más tiempo nos va tomar transferirlo por tanto tenemos una relación lineal.
tiempo transferencia = tiempo para transferir cantida * tamaño archivo + tiempo inicial, esto en notación de big O lo podríamos representar como O(n) entre mas grande el archivo mas tiempo nos 

tomaría y esto aumenta linealmente.
para el caso 2 llevar el archivo en un avión sin importar que tan grande es el archivo(podrían ser terabytes) el avión va tardar lo mismo (o una constante) en big O representamos esto como O(1)




este ejemplo creo que es muy bueno para entender la relevancia de la notación big O que nos muestra las diferencias de ejecución para cantidades enormes de datos, por ejemplo en general podemos decir que O(1) es mejor que O(n) pero si queremos transferir un archivo pequeño seguramente no lo vayamos hacer por un avion.