Bon.. je vous passe du sujet mais pour la petite histoire l'algo concerne la recherche de la plus courte tournée bitonique .
Je ne sais pas s'il y a une relation avec le tri bitonique, mais si quelqu'un le sait il peut me le dire

Ma question concerne l'exactitude de mon calcul du cout.
J'ai l'algo suivant:

(en C-like)

long_min(a,r){
    int i=max(a,r)+1;
    if (i>=tailleTab) return;
    return min(long_min(i,r)+dist(P[a],P[i]),
               long_min(a,i)+dist(P[i],P[r]));
}

Pour le cout, je dis
T(n) = T(n-1) + 4*(n-1)
(à un cas particulier près de n=1 peut etre...)

Ce qui donne un coùt en O(n²).

Cela vous semble juste?