Page 62 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

2S = n* (n+1), por lo tanto, S = n* (n+1) / 2. Utilizando la misma idea, se tiene:
n n

2S = n* (n-1), por lo tanto, S = n* (n-1) / 2. De esta forma se tiene:
n n
C = n* (n-1) / 2 = (n -n) / 2.
2
Entonces, el tiempo de ejecución del algoritmo es proporcional a O(n ).
2

Método de INSercIóN BINarIa

Este realiza una búsqueda binara, en lugar de una búsqueda secuencial, para insertar un elemento
en la parte izquierda del arreglo, que ya se encuentra ordenado. El proceso se repite desde el segun-
do hasta el n-ésimo elemento (algoritmo 2.4).

Algoritmo 2.4. Método de inserción binaria

56