Question

Problem #1: (15 points) You have two sorted lists of integers, L, and L2. You know the lengths of each list, L1 has length N, and L2 has length N2 (a) Design an efficient algorithm (only pseudocode) to output a sorted list L L2 (the intersection of L and L2). (b) If you know that N2> Ni. What is the running time complexity of your algorithm? Justify Important Note For this problem, you don't need to submit any implementation in Java. Only the pseudocode of your algorithm is required.

Answer 1

We have two sorted list of Integers. A) create two points temp 1 and temp 2 of type list L_1 and list L_2 respectively and point to two list respectively. If temp 1 is small then the temp 2 element then move temp 1 to next element by temp 1 = temp 1 rightarrow next. If temp 1 element size > temp 2 element then move temp 2 to next element by temp 2 = temp 2 rightarrow next If both are same point any of then a move temp 1 and temp 2 to thin next element. (b) If N_2 > N_1 running time complexity with be N_2 if difference b/w N_2 and N_1 is significantly high.