title: Calculate Big Theta Notation Bubble Sort
body: <p>I'm trying to calculate the theta notation for bubble sort but I'm getting stuck. Given this procedure (pseudocode):</p>
  
  <pre><code>procedure BUBBLE_SORT(A,n) {
      array A(1 to n)
      for (int i = 1; i &lt;= n; i++) {
          for(int j = 1; j &lt;= n-1; j++) {
              if(A[j] &gt; A[j+1] {
                  //swap(A(j), A(j+1))
              }
          }
      }
  }
  </code></pre>
  
  <p>I was able to get the worst case running time with sigma notation to be:</p>
  
  <p>(n^2 - n) / 2</p>
  
  <p>For the best case running time, I followed my book and did this:</p>
  
  <p>Given p(n) = (n^2 - n) / 2, we claim that p(n) = Θ(n^2). To prove this we show that for some constants c1, c2 and n0:</p>
  
  <p>C1n^2 &lt;= (n^2 / 2) + (n / 2) &lt;= C2n^2</p>
  
  <p>Dividing both sides by n^2, we get:</p>
  
  <p>C1 &lt;= (1 / 2) + (1 / 2n) &lt;= C2</p>
  
  <p>This is where I got lost. In the book, the author picked out some numbers, plugged them in and said "Therefore it follows that p(n) = Θ(n^2)"</p>
  
  <p>How do I know what numbers to plug in? Can I just plug in any numbers? And if those numbers do fit the inequality, does that mean I can immediately say that the algorithm is Θ(n^2)?</p>
  
  <p>Thank you!</p>