Page 24 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 24

INTRODUCCIÓN AL ANÁLISIS  DE ALGORITMOS


                                                 Figura 1.3. Cota inferior asintótica





































                  cota ajuStada aSINtótIca




                  Si f(n) =     (g(n)) y f(n) = O(g(n)), entonces f(n) =      (g(n)) si y solo si existen constantes positivas c y

                  n tal que para toda n > n , C  |g(n)| ≤ |f(n)| ≤ C |g(n)|.
                   o                      o  1                2
                  Esto indica que el peor y el mejor caso marcan la misma cantidad de tiempo (figura 1.4).



                                                Figura 1.4. Cota ajustada asintótica


























                                                               18
   19   20   21   22   23   24   25   26   27   28   29