Solución:
Es O(n). Es un algoritmo general, no puede encontrar el máximo / mínimo en el caso general sin verificarlos todos. Python ni siquiera tiene un tipo de colección ordenada incorporado que facilitaría la especialización de la comprobación.
A for El bucle tendría la misma complejidad algorítmica, pero se ejecutaría más lento en el caso típico, ya que min/max (en CPython de todos modos) están ejecutando un bucle equivalente en la capa C, evitando la sobrecarga del intérprete de código de bytes, que el for bucle incurriría.
Para encontrar el máximo o mínimo de una secuencia, debe mire cada elemento una vez, por lo que no puede ser mejor que O (n).
Por supuesto, Python min y max tener O (n) también: docs.
Puede escribir su propia función min / max con un bucle for y tendrá la misma complejidad, pero será más lenta porque no está optimizada en C.