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, Gilles May 9 '14 at 13:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What does the column of square-bracketed terms mean? Is "n2" a typo for "n^2"? $\endgroup$ – David Richerby Jan 31 '14 at 14:07
  • $\begingroup$ It's the ''cost'' of the operations. I did them on the best case, should they be there for the worst case? I'm supposed to also find the constant and that's why they are there. And yes, it's a typo $\endgroup$ – Badcoder Jan 31 '14 at 14:11
  • $\begingroup$ We have many questions on similar problems, see e.g. loops. $\endgroup$ – Raphael Jan 31 '14 at 14:20

There is just one loop in for, so the number of steps here will be proportional to n not n^2. The outer loop is running in a n proportional number of steps too. So The complexity of your algorithm is n^2.
N.B. : When speaking complexity, you don't have to state (n^2 + n) / 2,just say n^2 because they are the same for big ns.

  • 2
    $\begingroup$ 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. $\endgroup$ – FrankW Jan 31 '14 at 16:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.