El profesor menciona que la busqueda en un diccionario tiene complejidad O(1), no deberian ser O(n) donde n es el tamaño del diccionario?

no, O(n) es cuando la complejidad crece de forma lineal con forme crece el n pero en este caso el resultado esta presente guardado en un diccionario, de esta manera cuando lo consultes siempre será la misma complejidad

Precisamente iba a poster el enlace que deja @cristianblar. Adicionalmente, la explicación de @rolandorg es muy precisa. Que buena comunidad! Saludos!

¡Hola Aaron!

Aquí podrás encontrar la complejidad (en tiempo) de varias estructuras de datos en Python :)

O(n) significa que para realizar la operación, es necesario realizar n operaciones (no tan literal, pero por ahí va la idea). Si haces esta afirmación en el ámbito del diccionario, implicaría que tendrías que recorrer todo el diccionario de orden n para obtener una clave/valor y esto no es correcto. Las estructuras de datos tipo diccionario están optimizadas para obtener el valor de una clave de forma rápida, en una única operación, por eso su complejidad es O(1)

No, porque el diccionario esta organizado por un índice, tanto en sus llaves como en sus valores.

O(n) aplicaria si elelemento fuera un arreglo desordenado donde no se conoce el índice.