Calculating time complexity of a Iterative algorithm

Question

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?

I think what you're saying is true. max(m,n) is kind of a different way to express the same thing, but when there are two factors, e.g. vertices and edges, it's common practice to make no assumptions and write it like so. Don't take my word for it though, it just made me think of a lot of graph algorithms which are O(v+e). — keyser
– keyser, Commented Jan 11, 2015 at 20:57

kraskevich · Accepted Answer · 2015-01-11 20:59:55Z

4

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.

answered Jan 11, 2015 at 20:59

kraskevich

18.6k4 gold badges37 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Calculating time complexity of a Iterative algorithm

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related