Dans le pire des cas

* Tri fusion Ө(N log2 N)

* Tri insertion Ө(N²)

Nous nous intéressons à la modification du tri par fusion de n/k sous listes de longueur k triées via le tri par insertion puis fusionner à l'aide du mécanisme de fusion classique.

1)       Montrer que les n/k sous listes, chacune de longueur k peuvent être triées via le tri par insertion avec un temps Ө(Nk) dans le cas le plus défavorable.

2)       Montrer que les sous listes peuvent être fusionnées en Ө(N log2 N/k) dans le cas le plus défavorable

3)       En déduire que le comportement asymptotique de l'algorithme modifié dans le pire des cas est Ө(Nk + N log2 N/k)

4)       Montrer que si k= Ө(log2 N) l'algorithme modifié a le même temps d'exécution asymptotique que le tri par fusion classique

J'aurai besoin d'une correction détailléé de la question 3 et 4 que je risque d'avoir en ds. La correction n'a pas été fini en cours et nous ne l'aurons pas.
Je suis en IUP génie mathématiques et informatique
MErci beaucoup!