title: How to analyse complexity of the given optimized bubble sort?
body: <p>This is a pseudo code of optimized bubble sort algorithm. I have tried to analyze its time complexity, but i am not sure what is the cost of line 4 (if A[i-1] > A[i]). Is the answer (n-1)+(n-2)+........+1 ? Also what would be the cost of lines 5 to 8?</p>
  
  <pre><code>1.for j = A.length to 2
  2.    swapped = false
  3.    for i = 2 to j
  4.        if A[i-1] &gt; A[i]
  5.            temp = A[i]
  6.            A[i-1] = A[i]
  7.            A[i-1] = temp
  8.            swapped = true
  9.    if(!swapped)
  10.       break
  </code></pre>