CODEWITHSUNDEEP
java
jhonny alcantara
jhonny alcantara

Reputation: 9

What is the big O running time of the following code?

public static int Count( List<Integer> lst1, List<Integer> lst2)
{
    Iterator<Integer> itr1 = lst1.iterator();

    int count=0;
    while ( itr1.hasNext() )
    {
        Integer x = itr1.next();
        Iterator<Integer> itr2 = lst2.iterator();
        while ( itr2.hasNext() )
            if ( x.equals( itr2.next()) )
                count++;
    }

    return count;
}
  1. If an ArrayList is passed for lst1 and lst2.
  2. If a LinkedList is passed for lst1 and lst2.

I go for both because for the fist while loop O(n) then the secong while O(n) and the if also O(n) = O(n^3). I dont know if I am wrong or not?

Upvotes: 0

Views: 391

Answers (2)

Steve P.
Steve P.

Reputation: 14699

It's O(size(lst1)*size(lst2)). For all xi in lst1, you compare xi to every element in lst2. In this case, it's more accurately Θ(size(lst1)*size(lst2)), since it's bounded both above and below by size(lst1)*size(lst2).

Upvotes: 6

Suresh Atta
Suresh Atta

Reputation: 121998

No doubt.. @steven gave a nice mathematical rep. The big O happening here is the multiplication of the sizes of lists providing to the method.

Because with each element in the list1 is comparing with each element in the list2..So that the loop runs for SizeofList1*SizeOfLit2.

Here is beginner guide with loops.Hope you will get it.

Upvotes: 0

Related Questions