Complexité : simplifier et dominer une somme

[PythagoreSauvage]

Bonjour à tous, je suis en train de calculer la complexité d'un algorithme et je tombe sur une somme, que je n'arrive pas à simplifier, et dont j'essaye d'extraire un :

Soit . J'ai la somme suivante :

que je n'arrive pas à dominer/majorer

Si quelqu'un à une idée,
D'avance merci

[tournesol]

La majoration est calculable.

[tournesol]

Ma réponse précédente est égale à qui est un

[PythagoreSauvage]

AH oui c'est tout à fait exact, je ne sais pas si c'est pas trop brutal comme majoration mais à mon avis c'est la manière la plus simple je dirais, ou la seule qui permet d'avoir un résultat exploitable

[Skullkid]

Bonjour, on peut également majorer crûment par qui donne du . Ça donne une meilleure borne pour les petites valeurs de c.

[PythagoreSauvage]

AH oui pas mal merci Skullkid, d'autant qu'on a une borne sur c en fait (qui dépend d'un autre paramètre k < m, on sait que c <= (m-k)/2