Part I: Algorithm Analysis

$1.$ You are given two linked lists with O$($n$)$ elements. You are asked to find the intersection of two lists. Assume that the sets don$$t have duplicates and not sorted, and also assume that comparison operation is a simple statement and it takes O$(1)$ time.

a$.$ Please provide a pseudo code that has the growth rate of O$($n$2)$

b$.$ Improve your solution, and give a pseudo code that has a better growth rate which is O$($nlogn$).$

c$.$ Is it possible to make it O$($n$)?$ Please provide a pseudo code for your solution, if any.

Note: You can call other functions use other data structures, you don$$t need to give pseudocodes for those functions. Just know their run time complexity.

$2.$ You are given the following pseudocode for an algorithm:

$1$ method$1($n$)$

$2$ if n$==0$

$3$ return $0$

$4$ else

$5$ return method$2($n$-1,$ n$-1)($n$-1)$

$6$ method$2($m$,$ k$)$

$7$ if m$==0$

$8$ return method$1($k$)$

$9$ else

$10$ return $1+$ method$2($m$-1,$ k$)$

a$.$ What would be the output for the following method call?

System.out.println$($method$1(4))$;

b$.$ Please provide the recurrence form for the running time function of this algorithm.

c$.$ Please find the growth rate of the algorithm in Big$-$O notation.