# Bubble sort complexity [duplicate]

So I have this code:

done <- false                                     [1]
n <- 0                                            [1]
while (n < a) and (done = false)                  [(n+1)(1+1+1)]
done <- true                                    [n]
for m <- (a- 1) downto n                        [n(1+1+1+1)]
if list[m] < list[m - 1] then                [n]
tmp <- list[m]                             [n]
list[m] <- list[m-1]                       [n]
list[m - 1] <- tmp                         [n]
done <- false                              [n]
n <- n + 1                                   [1]
return list                                       [1]

Am I doing this right? My conclusions are that the inne for-loop runs (n^2 + n) / 2 times and the outher while-loop runs n+1 times. I don't know how to properly argue for that the bubble sort has the complexity O(n^2)

## marked as duplicate by FrankW, Wandering Logic, GillesMay 9 '14 at 13:34

• The number of steps in the inner loop being proportional to $n^2$ refers to the aggregate over all iterations of the outer loop. Also, $n^2$ is not the same as $\frac{n^2+n}2$, no matter how large $n$ might get. – FrankW Jan 31 '14 at 16:50