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 List union(List ls1, List 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 List intersection(List ls1, List ls2) { // TODO return null; } /** * Simple testing to get you started. Add more tests of your own! */ public static void main(String... args) { List 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 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 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