def findDupes (A, B): # Find all elements common to sequences A and B and return them as a list

 """Rhttp://localhost:8888/notebooks/IT-309%20A1%20Problems%20and%20Blank%20Submission%20Template(1).ipynb#P6,-Q2:--What-is-the-big-Oh-family-for-the-above-code?--Put-the-response-in-the-next-cell.eturn a list of all element common to the sequences (lists) A and B."""

 rlist = [ ]

 for a in A:

 for b in B:

 if a == b:

 rlist.append(a)

 return rlist 

The code below tests the above function by defining two sequences of size 1000 and 500, respectively, then running the function using them as input. All elements of the second will be in the first. The code uses the built-in time function to measure the start and end times. Run the code below to see the result. Don't forget to run the cell that has the function definition to put it in your name space. Also be patient - the answer might take up to a minute to appear.

from time import time S1 = [n for n in range(0, 1000)] S2 = [n for n in range(0, 1000, 2) ] start = time() x = findDupes(S1, S2) print('Time: ', time() - start, ' # elts: ', len(x))

P6, Q4: Cut and paste the above code in the above cell into the next one, modify it to change both the sequence sizes to 10,000 (the second sequence only selected every other element, so will be 5,000), rerun the code and note the results. Then rerun it multiple times for sequences of 20,000, 30,000, 40,000, and 60,000 and note the results. Enter the resulting times in the cell below.

10,000:

20,000:

30,000:

40,000:

60,000:

Review your results for the various runs above. Is doubling the input size, say from 10,000 to 20,000 or from 20,000 to 40,000 consistent with the big-Oh prediction?

from time import time

S1 = [n for n in range(0, 40000)] S2 = [n for n in range(0, 40000, 2) ] start = time() x = findDupes(S1, S2) print('Time: ', time() - start, ' # elts: ', len(x))