07.09.2021

Problema 1: Para cada función f(n) y tiempo t en la siguiente tabla,
determine el tamaño n más grande para un problema que puede ser resuelto 
en un tiempo t, asumiento que el algoritmo toma f(n) microsegundos
para resolver el problema.

           1       1      1    1   1   1    1
        segundo  minuto  hora day mes año siglo
lg n
sqrt(2)
n
n lg n
n^2
2^n
n!

Problema 2: Considere el problema de ordenar n números almacenados en un
arreglo A, encontrando primero el elemento más pequeño de A e intercambiándolo
por el elementro A[1]. Entonces encuentre el segundo elemento más pequeño
de A y se intercambia con el elemento A[2]. Continúe de esta manera para los
primeros n-1 elementos de A. Escriba un pseudocódigo para este algoritmo,
el cual se conoce como "ordenamiento por selección".

 a) ¿Qué invariante de ciclo mantiene este algoritmo?
 b) ¿Porqué necesita ejecutarse solamente para los primeros n-1 alementos y no
    para todos los n elementos?
 c) De el mejor tiempo de ejecución y el peor tiempo de ejecución en notación
    Theta.
 d) Programe en python el algoritmo y muestre algunas pruebas de ejecución.