In this question, we give two implementations for the function: def intersection_list (lst1, lst2) This function is given two lists of integers lst1 and lst2. When called, it will create and return a list containing all the elements that appear in both lists. For example, the call: intersection_list ([3, 9, 2, 7, 1], [4, 1, 8, 2]) could create and return the list [2, 1]. Note: You may assume that each list does not contain duplicate items. a) Give an implementation for intersection_list with the best worst-case runtime. b) Give an implementation for intersection_list with the best average-case runtime.

see explaination

Explanation:

a) Worst Case-time complexity=O (n)

def intersection_list (lst1, lst2):

lst3 = [value for value in lst1 if value in lst2]

return lst3

lst1 = []

lst2 = []

n1 = int (input ("Enter number of elements for list1 : "))

for i in range (0, n1):

ele = int (input ())

lst1. append (ele) # adding the element

n2 = int (input ("Enter number of elements for list2 : "))

for i in range (0, n2):

ele = int (input ())

lst2. append (ele) # adding the element

print (intersection_list (lst1, lst2))

b) Average case-time complexity=O (min (len (lst1), len (lst2))

def intersection_list (lst1, lst2):

return list (set (lst1) & set (lst2))

lst1 = []

lst2 = []

n1 = int (input ("Enter number of elements for list1 : "))

for i in range (0, n1):

ele = int (input ())

lst1. append (ele)

n2 = int (input ("Enter number of elements for list2 : "))

for i in range (0, n2):

ele = int (input ())

lst2. append (ele)

print (intersection_list (lst1, lst2))