Question

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.

Answer 1

see explaination

Step-by-step 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))