Il secondo algoritmo che hai proposto, nel caso pessimo, ha sempre una complessita' di n^2 (n = size), cosi' come la complessita' del primo algoritmo...

L'unica differenza sta negli altri casi: ad es. caso ottimo -> array gia' ordinato: il II algoritmo entra una volta sola nel ciclo for (complessità lineare...)
Mentre il primo algoritmo ha ancora complessità n^2.

Considerando il caso peggiore quindi il bubblesort nella prima versione costa tanto quanto la seconda versione.

Ciao.