Juan Camilo Muñoz Castelblanco.
257120
Average time formula for Insertion Sort when input is
a uniform random permutation with repetitions.
Se había deducido
que Para el tiempo promedio se igualaba tj
= (i + 1)/2 quedando:
la cual al resolver nos dio la formula
general del tiempo promedio para insertion sort:
Con el Applet de insertion sort con permutaciones con repeticiones obtenemos los
valores para t(3), t(4) y t(5); y formulamos el
siguiente sistema de ecuaciones:
Resolviéndolo:
Por lo que la formula para el tiempo promedio de insertion
sort con permutaciones con repeticiones queda:
