) a le bon comportement asymptotique et dire qu'elle est le meilleur majorant possible de la complexité (enfin la complexité c'est pas très précis, mais le sens pourrait être « nombre de possibilités à examiner dans le pire cas ») sont deux choses différentes... (quoique je pinaille, si tu veux un O(complexité dans le pire cas), c'est-à-dire que ta suite majore la complexité *à un facteur constant près*, alors seul le comportement asymptotique est important, c'est vrai)
Sinon l'associativité signifie que dès que dans ton arbre tu as deux nœuds + ou × en relation père-fils tu peux les permuter, donc je ne vois pas ce qui te permet de penser que ça a moins d'influence s'il y a plus d'opérateurs : plus tu as d'opérateurs plus tu peux rencontrer cette relation... alors on pourrait penser que ça réduit la cardinalité d'un facteur constant (auquel cas ça ne change rien au O) mais la réduire d'un facteur qui tend vers 1, ça ne me semble pas très réaliste.
pour les soustractions et les divisions on s'est contenté de dire qu'elles n'étaient définies que pour un seul ordre des nombres, donc on fait comme si ces opérateurs étaient commutatifs, ça n'a pas de rapport avec l'associativité ^^