Question: Analyze the time complexity of this program in big-O notation, assuming the size of L1 is n and the size of L2 is n too

Analyze the time complexity of this program in big-O notation, assuming the size of L1 is n and the size of L2 is n too

public static > void intersection(List L1, List L2, List Intersect) {

ListIterator iterL1 = L1.listIterator(); ListIterator iterL2 = L2.listIterator();

AnyType itemL1=null, itemL2=null;

// get first item in each list if ( iterL1.hasNext() && iterL2.hasNext() ) { itemL1 = iterL1.next(); itemL2 = iterL2.next(); }

while ( itemL1 != null && itemL2 != null ) { int compareResult = itemL1.compareTo(itemL2);

if ( compareResult == 0 ) { Intersect.add(itemL1); itemL1 = iterL1.hasNext()?iterL1.next():null; itemL2 = iterL2.hasNext()?iterL2.next():null; } else if ( compareResult < 0 ) { itemL1 = iterL1.hasNext()?iterL1.next():null; } else { itemL2 = iterL2.hasNext()?iterL2.next():null; } } }

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!