CODEWITHSUNDEEP
javaalgorithmlinked-list
user1010101
user1010101

Reputation: 1658

Calculating time complexity of a Iterative algorithm

I am dealing with a problem where two singly linked list merge at some point. Following image illustrates this concept.

enter image description here

I am suppose to find and return the node where they both intersect. I am only given the reference to head of both lists. Following is the algorithm i came up with.

public Node getNodeIntersection(Node head1, Node head2)
{
     Node temp1 = head1;
     Node temp2 = head2;
     /*Get lengths of both the lists*/
     int len1 = this.getLength(temp1);
     int len2 = this.getLength(temp2);

     int diff = getAbs(len1,len2); //get absolute difference of the two lengths

     //Iterate through the bigger list first so both list have equal nodes left
     if(len1 > len2)
     {
        int count = 0;
        while(count < diff)
        {
            temp1 = temp1.getNext();
            count++;
        }
     }
     else
     {
             int count = 0;
            while(count < diff)
        {
            temp2 = temp2.getNext();
            count++;
        }
     }

     Node nIntersect = null;
     while(temp1 != temp2)
     {
        temp1 = temp1.getNext();
        temp2 = temp2.getNext();

        if(temp1 == temp2)
        {
            nIntersect = temp1;
        }

     }

     return nIntersect;

}

I am having trouble calculating the time complexity for this. My understanding is that I first find lengths of both the list which would be N + N. Then I iterate through the bigger list first which is again N and then i iterate through both the lists till they intersect which is again N nodes. I was thinking that that time complexity for this algorithm would be O(N). To my surprise after solving this algorithm i found similar solutions on some blogs and the time complexity for this is O(M+N). I don't understand why? I thought that as N goes to infinite The larger value would dominate so it would be O(max(m,n)) which would either be O(n) or O(m) depending on which one is larger. Can someone please clarify this for me?

Upvotes: 1

Views: 72

Answers (1)

kraskevich
kraskevich

Reputation: 18586

O(max(n, m)) is O(n + m) because max(n, m) <= n + m. It is a precise bound because max(n, m) >= (n + m) / 2.

Upvotes: 4

Related Questions