While we drop the constant in big O notation, does it matter in real-life situations?

Question

While I understand that big O 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.

To print the value of a node in a linked list k places from the end of the list.

Given a node:

/* Link list node */
struct node
{
  int data;
  struct node* next;
};

Solution 1 O(n)

This solution iterates over the list twice, once to find the length of the list, and the second time to get to the end of the list - N.

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->next;
        len++;
    }

    // Check if value of n is not more than length of the linked list
    if (len < n)
      return;

    temp = head;

    // 2) Get the (n-len+1)th node from the begining
    for (i = 1; i < len-n+1; i++)
    {
       temp = temp->next;
    }
    printf ("%d", temp->data);

    return;
}

Solution 2 O(n)

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).

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 < n )
     {
        if(ref_ptr == NULL)
        {
           return;
        }
        ref_ptr = ref_ptr->next;
        count++;
     }

     while(ref_ptr != NULL)
     {
        main_ptr = main_ptr->next;
        ref_ptr  = ref_ptr->next;
     }
  }
}

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?

Answer 1

Yes. In the specific example where the same work occurs, a single loop is likely to be more efficient than looping over a set of data twice. But the idea of O(2n) ~ O(n) is that 2 ns vs 1 ns may not really matter. Big O works better to show how a piece of code might scale, e.g. if you made the loop O(n^2) then the difference of O(n) vs O(2n) is much less than O(n) vs O(n^2).

If your linked list contains terrabytes of data, then it might be worth reducing to the single loop iteration. A big O metric, in this case may not be sufficient to describe your worst case; you would be better off timing the code and considering the needs of the application.

Another example is in embedded software, where 1 ms vs 2 ms could be the difference between a 500 Hz and a 1 kHz control loop.

The lesson learned is that it depends on the application.

Answer 2

The constant only matters if the order is the same, and the operations are comparable in complexity. If they aren't of the same order, then the one with the higher order is guaranteed to take longer once you have a large enough n. Sometimes n must be larger than your typical data set, and the only way to pick the most efficient algorithm is to benchmark them.