Cita:
Iniciado por sam90 
en el primer caso sopungamos que es n log n.....para el proximo el array ya esta ordenado asi que desde la segunda hasta el fin siempre va a tarde n^2...asi que debera quedar en algo asi como un: n^3 log n
Si consideramos lo que indicas, lo que es en mi opinion correcto, es decir que la primera vez deja el arreglo ordenado y luego es el peor de los casos, entonces queda
n log n + (n-1)*n^2, i.e. esta acotado por n^3. No es tan grande como n^3 log n.