Bonsoir
J'espère pouvoir trouver l'aide dont j'aurai besoin ici

En cours de complexité des algorithmes, on nous a donné un exercice à faire assez ... bref, je vous laisse découvrir.

En gros il s'agit de calculer la complexité dans le pire des cas d'un algo manipulant la matrice d'un graphe (simple non orienté quelconque), en fonction du nombre de ses arrêtes (on pose k) et ... du nombre de ses sommets (posons n) et de finalement associer le problème à sa classe de problèmes adéquates (en ce qui nous concerne, résolubles en FPT ou pas).

Je comprends que je dois trouver un O(f(k)g(n)), ici en l'occurrence je suis tombé sur un assez banal O(f(k)n²)

J'ai aussi réussi à isoler f(k) (dont l'expression nous importe peu ici).

Le problème c'est que je ne sais pas si pour le calcul dans le pire des cas on choisit k = n+1 (d'après l'énoncé, le nombre minimal d'arrêtes) ou k= n(n+1)/2 (nombre max d'arrêtes) (donc, dans les deux cas ci présent, l'algo n'est plus en FPT, puisqu'il dépend uniquement de n non plus de k) ou un k arbitraire mais majoré par un O(n²) et minoré par O(n) (impliquant donc qu'il doit être classé parmi les problèmes résolubles en FPT).

Je vous remercie d'avance rien que pour votre lecture et encore plus pour vos réponses
excellentes fin de soirée à tous