title: Is Big O time complexity of this sorting code n^2?
body: <p>We know that bubble sort of array has time complexity of O(n^2).</p>
  
  <p>I thought of using bubble sort to sort a singly linked-list.</p>
  
  <p>Below is my C code. (<code>head</code> of list is passed by refernce to <code>headRef</code>). It does sort correctly, but my problem  is I find the concept of time-complexity a bit confusing, so although I think my below code also has complexity of O(n^2), I am not sure.</p>
  
  <pre><code>void sortNodes(struct node **headRef)
  {
      struct node *head;
      int i, j, k;
      struct node *node_Pointer;
      struct node *node_Pointer_Left, *node_Pointer_Left_Left, *hold;
      printf("\nSorting started !\n--------------------\n");
  
      for (i=1; i&lt;N; i++)
      {
              head = *headRef;
              node_Pointer = head;
              for(j=1;j&lt;N;j++)
              {
                      {
                              // Making node_Pointer point to the jth node.
                              // Making node_Pointer_Left point to (j-1)th node.
                              // Making node_Pointer_Left_Left point to (j-2)th node. 
                              if (j &gt; 1)
                                      node_Pointer_Left_Left = node_Pointer_Left;
                              node_Pointer_Left = node_Pointer;
                              node_Pointer = node_Pointer-&gt;next;
                      }
  
                      if ( node_Pointer-&gt;data &lt; node_Pointer_Left-&gt;data )
                      {
                              //Below  part sorts by changing pointers.
                              //If you want to sort by swapping data, please comment below part.
                              //and uncomment the bottom part.
                              struct node *old_J_next = node_Pointer-&gt;next;
                              node_Pointer-&gt;next = node_Pointer_Left;
                              node_Pointer_Left-&gt;next = old_J_next;
                              if (j ==1)
                                      *headRef  = node_Pointer;
                                else
                                      node_Pointer_Left_Left-&gt;next = node_Pointer;
  
                              hold = node_Pointer;
                              node_Pointer = node_Pointer_Left;
                              node_Pointer_Left = hold;
  
                              //Below commented part sorts by changing (swapping) the data.
                              /*{
                                      int temp = node_Pointer-&gt;data;
                                      node_Pointer-&gt;data = node_Pointer_Left-&gt;data;
                                      node_Pointer_Left-&gt;data = temp;
                              }*/
                      }
              }
      }
      printf("sorting finished !\n");
  
  }
  </code></pre>
  
  <p>Please confirm if the times complexity of above code is O(N^2).</p>
  
  <p>My analysis: Outer for loop executes N-1 times and for each iteration of outer for loop, inner for loop executes N-1 times.And, for each iteration of inner for loop, there are some 'constant' number of statements which are executed. So total execution (approximate) = (N-1) * ((N-1)*constant) which will be of the order N^2.</p>
  
  <p>Sadly, I am not confident that my analysis is correct, so I am posting it here. Would really thank if you told if it is right or wrong.  </p>