title: While we drop the constant in big O notation, does it matter in real-life situations?
body: <p>While I understand that <a href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noreferrer">big O</a> notation simply describes the growth rate of an algorithm, I'm uncertain if there is any difference in efficiency in real life between the following O(n) algorithms.</p>
  
  <p>To print the value of a node in a linked list k places from the end of the list.</p>
  
  <p>Given a node:</p>
  
  <pre><code>/* Link list node */
  struct node
  {
    int data;
    struct node* next;
  };
  </code></pre>
  
  <p><strong>Solution 1 O(n)</strong></p>
  
  <p>This solution iterates over the list twice, once to find the length of the list, and the second time to get to the <strong>end of the list - N</strong>.</p>
  
  <pre><code>void printNthFromLast(struct node* head, int n)
  {
      int len = 0, i;
      struct node *temp = head;
  
  
      // 1) Count the number of nodes in Linked List
      while (temp != NULL)
      {
          temp = temp-&gt;next;
          len++;
      }
  
      // Check if value of n is not more than length of the linked list
      if (len &lt; n)
        return;
  
      temp = head;
  
      // 2) Get the (n-len+1)th node from the begining
      for (i = 1; i &lt; len-n+1; i++)
      {
         temp = temp-&gt;next;
      }
      printf ("%d", temp-&gt;data);
  
      return;
  }
  </code></pre>
  
  <p><strong>Solution 2 O(n)</strong></p>
  
  <p>This solution only iterates over the list once. The ref_ptr pointer leads, and a second pointer (main_ptr) follows it k places behind. When ref_ptr reaches the end of the list, main_ptr should be pointing at the correct node (k places from the end of the list).</p>
  
  <pre><code>void printNthFromLast(struct node *head, int n)
  {
    struct node *main_ptr = head;
    struct node *ref_ptr = head;
  
    int count = 0;
    if(head != NULL)
    {
      while( count &lt; n )
       {
          if(ref_ptr == NULL)
          {
             return;
          }
          ref_ptr = ref_ptr-&gt;next;
          count++;
       }
  
       while(ref_ptr != NULL)
       {
          main_ptr = main_ptr-&gt;next;
          ref_ptr  = ref_ptr-&gt;next;
       }
    }
  }
  </code></pre>
  
  <p>The question is: Even though both solutions are O(n) while leaving big O notation aside, is the second solution more efficient that the first for a very long list as it only iterates over the list once?</p>