title: why is the time complexity of bubble sort's best case being O(n)
body: <p>I deduced the time complexity of bubble sort in its best case according to the mothod used in book <strong>ALGORITHMS</strong> 2.2. But the answer turned out to be O(n^2).</p>
  
  <p>Here's my derivation, hope anyone can help me find out where is wrong:</p>
  
  <pre><code>public void bubbleSort(int arr[]) {
  for(int i = 0, len = arr.length; i &lt; len - 1; i++) {
      for(int j = 0; j &lt; len - i - 1; j++) {
          if(arr[j + 1] &lt; arr[j])
              swap(arr, j, j + 1);
      }
  }
  </code></pre>
  
  <p>}</p>
  
  <pre><code>Statements                      cost    times
  i = 0,len = arr.length          c1          1
  i &lt; len - 1                     c2          n
  i++                             c3          n - 1
  j = 0                           c4          n - 1
  j &lt; len - i - 1                 c5          t1(i=0) + t1(i=1) + ... + t1(i = n-2)
  j++                             c6          t2(i=0) + t2(i=1) + ... + t2(i = n-2)
  arr[j + 1] &lt; arr[j]             c7          t3(i=0) + t3(i=1) + ... + t3(i = n-2)
  swap(arr, j, j + 1)             c8          t4(i=0) + t4(i=1) + ... + t4(i = n-2)
  </code></pre>
  
  <p>T(n) = c1 + c2n + c3(n - 1) + c4(n - 1) + c5t5 + c6t6 + c7t7 + c8t8
       = c1 + c2n + c3(n - 1) + c4(n - 1) + c5[t1(i=0) + t1(i=1) + ... + t1(i = n-2)] + c6[t2(i=0) + t2(i=1) + ... + t2(i = n-2)] + c7[t3(i=0) + t3(i=1) + ... + t3(i = n-2)] + c8[t4(i=0) + t4(i=1) + ... + t4(i = n-2)];</p>
  
  <p>in its best cast, the sequence is already positive before sorting. Then t8 sould be 0.</p>
  
  <p>T(n) = c1 + c2n + c3(n - 1) + c4(n - 1) + c5[t1(i=0) + t1(i=1) + ... + t1(i = n-2)] + c6[t2(i=0) + t2(i=1) + ... + t2(i = n-2)] + c7[t3(i=0) + t3(i=1) + ... + t3(i = n-2)]</p>
  
  <p>The time complexity is O(n^2)</p>