Caveat lector

Ça manque de définition pour «satisfaisant», ta remarque est trop floue. Par exemple, pour des orgies, j'imagine que quadratique est le minimum requis pour que ça soit satisfaisant. Pour une certaine acception de «satisfaisant».

Je sous-entendais « le moins, le mieux ». Le credo en arithmétique des grands entiers, c'est d'avoir tout quasi-linéaire !

C'est marrant comme coincidence, j'ai aussi hier soir eu un repas (entre collègues) où on a utilisé un protocole de complexité quadratique impliquant des chocs de verres remplis de champagne.

Mais mes remarques, curieusement, n'étaient pas du même niveau... plutôt du genre "Trinquons, moi je fais le train, vous vous faites ce que vous voulez". Bon d'accord je me suis retenu quand la patronne s'est insérée dans le protocole.

Je croyais que les gens qui font de l'arithmétique comptaient la complexité par rapport au nombre de chiffres du nombre entré (la taille des données quoi).

Donc ton protocole là, il est en log(n), je ne vois pas de quoi tu te plains...

La taille des données dans le contexte que je décris, c'est le nombre de participants. Et il y a des rigolos qui ajoutent des contraintes supplémentaires qui limitent le parallélisme, du genre interdiction de croiser les bras avec ceux d'autres participants en train de trinquer.