Ecuación de recurrencia para el algoritmo de clasificación - algoritmo, recurrencia

Tengo la siguiente pregunta sobre una tarea y no estoy seguro de cómo abordarla

Supongamos que tenemos el siguiente algoritmo de clasificación:

Para ordenar una matriz de tamaño N (A [1 ... N]), el algoritmo hará lo siguiente:

1. Recursivamente, ordena los primeros elementos N-1 A [1… N-1]
2. Use la búsqueda binaria para encontrar el lugar correcto de A [N] para agregarlo a la lista ordenada. Después de encontrar el lugar correcto, deberá cambiar los valores para dar lugar a A [N].

Escriba la ecuación de recurrencia detallada para este algoritmo (no omita ningún término).

Respuestas

dónde C es algo constante

Veamos de dónde viene cada término en el n > 1 caso:

• T_ {n - 1}

Recursivamente, ordena los primeros elementos N-1 A [1… N-1]

• registro n

Use la búsqueda binaria para encontrar el lugar correcto de A [N] para agregarlo a la lista ordenada

• norte

Después de encontrar el lugar correcto, deberá cambiar los valores para dar lugar a A [N].

Sea T (n) el tiempo de ejecución del algoritmoDescrito para una matriz de n elementos. Primero, recursivamente se llama a sí mismo en los primeros elementos n-1, lo que nos da un costo de T (n-1). Luego, utiliza la búsqueda binaria para encontrar la posición del elemento en la posición original n, por lo que toma tiempo de registro (n-1). Finalmente, cambia los elementos (como máximo n-1 de ellos) para hacer espacio para el nuevo, lo que requiere un máximo de n pasos.

Poniendo las piezas juntas, obtenemos T (n) <=T (n-1) + log (n-1) + n - 1. Finalmente, dado que no especificó el caso base, asumo que el algoritmo simplemente no hace nada en una lista vacía (por lo tanto, la clasificación es trivial) y luego aparece T (0) = 0.