How to determine the space and time complexity of these two algorithms?

Question

I was practicing one algorithm exercise today from HackerRank: https://www.hackerrank.com/challenges/find-the-merge-point-of-two-joined-linked-lists

I decided to solve this problem with two solutions.

First algorithm, based on Floyd's algorithm:

/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  class Node {
     int data;
     Node next;
  }
*/
int FindMergeNode(Node headA, Node headB) {
    // Complete this function
    // Do not write the main method. 
    int length1 = countLength(headA);
    int length2 = countLength(headB);
    int d = Math.abs(length1 - length2);

    return (length1 > length2) ?
        findIntersection(d, headA, headB) : findIntersection(d, headB, headA);
}

int countLength(Node head) {
    Node current = head;
    int counter = 0;

    while (current != null) {
        current = current.next;
        counter++;
    }

    return counter;
}

int findIntersection(int d, Node headA, Node headB) {
    Node currentA = headA;
    Node currentB = headB;

    for (int i = 0; i < d; i++) {
        currentA = currentA.next;
    }

    while (currentA != null && currentB != null) {
        if (currentA == currentB) return currentA.data;

        currentA = currentA.next;
        currentB = currentB.next;
    }

    return -1;
}

Second algorithm, using one outer and inner loop:

/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  class Node {
     int data;
     Node next;
  }
*/
int FindMergeNode(Node headA, Node headB) {
    Node currentA = headA;

    while (currentA != null) {
        Node currentB = headB;

        while (currentB != null) {
            if (currentA == currentB) {
                return currentA.data;
            }

            currentB = currentB.next;
        }

        currentA = currentA.next;
    }

    return -1;
}

Honestly, I'm sure that the first algorithm is better than the second because of its performance. I would like to demonstrate this performance using SPACE and TIME COMPLEXITY, I have not dominated those topics.

According to the material, this solution should be Time Complexity: O(N). But I'm not quite sure that the first algorithm will be O(N).

Answer 1

The first algorithm scans headA and headB once to find the lengths, then skips the extra elements of the longer chain, then scans in parallel the two chains. The time complexity is proportional to the length of the chains, so it is O(N). It doesn't matter if you scan the lists 2, 3, or 5 times, as long as that number is constant, the time complexity is still O(N).

The second algorithm is worse, for each element in headA before the merge point, it scans the entire headB. In the worst case, when the lists don't intersect at the last node, it will scan all elements of headB for each element of headA. So the time complexity of this is O(N^2).

The space complexity of both algorithms is O(1), because you use constant storage in both (a bunch of local variables), that don't change, regardless the size of the input lists.