Do not assume the lists L1 and L2 are sorted. State the big-Oh running time of e

Question

Do not assume the lists L1 and L2 are sorted. State the big-Oh running time of each method and then write a brief explanation to justify your answer. For the analysis, you may assume that L1and L2 are both of length n, although your code should work properly for lists of differing lengths. Below is the starter code:

public class SetOps {
  
/**
* Returns a list (without duplicates) containing all the items
* in ls1 plus all the items in ls2. Note: ls1 and ls2 are
* unchanged by this method.
*/
public static <T> List<T> union(List<T> ls1, List<T> ls2) {
// TODO
return null;
}

/**
* Returns a list (without duplicates) of all the items which
* appear both in ls1 and in ls2. Note: ls1 and ls2 are
* unchanged by this method.
*/
public static <T> List<T> intersection(List<T> ls1, List<T> ls2) {
// TODO
return null;
}
  
/**
* Simple testing to get you started. Add more tests of your own!
*/
public static void main(String... args) {
List<String> ls1 = new DoublyLinkedList<>();
ls1.add("ant");
ls1.add("bat");
ls1.add("cat");
ls1.add("ant"); // this is a duplicate element
ls1.add("fox");
int n1 = ls1.size();
System.out.println("ls1 = " + ls1);
  
List<String> ls2 = new DoublyLinkedList<>();
ls2.add("cat");
ls2.add("dog");
ls2.add("dog"); // this is a duplicate element
ls2.add("emu");
ls2.add("fox");
ls2.add("gnu");
int n2 = ls2.size();
System.out.println("ls2 = " + ls2);
  
List<String> ls3, ls4;
ls3 = union(ls1, ls2);
assert n1 == ls1.size();
assert n2 == ls2.size();
assert 7 == ls3.size();
System.out.println("ls3 = " + ls3);

ls4 = intersection(ls1, ls2);
assert n1 == ls1.size();
assert n2 == ls2.size();
assert 2 == ls4.size();
System.out.println("ls4 = " + ls4);
}
}

Given two sorted lists, L1 and L2, write a procedure to compute Li nL2 using only the basic list operations. Given two sorted lists, L1 and L2, write a procedure to compute L1 UL2 using only the basic list operations. 3.4 3.5

Explanation / Answer

Since, you have not shared your list class, i have assumed some methods and wrote code on basis. In case of any issues, let me know via comments.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.