Oui, tu sais que

Une telle écriture existe puisque k < n ? Ça ne me paraît pas évident... Pourrais-tu m'indiquer cette écriture ou bien un point de départ pour l'obtenir s'il te plaît ?

Je veux dire : pour le moment la complexité est O(2ⁿ), mais si ça se trouve en passant par une écriture « inférieure » on pourrait la définir plus précisément et obtenir quelque chose comme O(2^k) par exemple.

k est un entier, n est un entier. Donc si k<n, alors . Donc tu peux améliorer la majoration grâce à une somme allant de 1 à n-1 au lieu de 1 à n.

Dans ce cas, non.

OK, merci !