Homework 9: Big O – Searching – Sorting

CS 1301 - Introduction to Computing
Homework 9: Big O – Searching – Sorting

1. [20pts]: For each of the following pieces of code, write down the time complexity that the
code will run in, choosing from O(1), O(log n), O(n), O(n log n), O(n2
), O(n3
):
for i in range(n):
 i *= 2
 for j in range(n):
 print(i * j)
Big-O:________________________________
for i in range(10):
 for j in range(n):
 print(i-j)
Big-O: _____________________________
for i in range(n):
 for j in range(n, n/3, -9):
 for k in range(n):
 return n

Big-O:________________________________
for i in range(521313*2213*11):
 for j in range(i ** i ** i):
 for y in range(j * i):
 print(i, j, y)
Big-O:_____________________________
i = 0;
while i < n:
 print(“David” * i)
 i *= 2
 i += 1
Big-O:________________________________
for i in range(len(“McDonald”)):
 print(“hi”)
 j = 0;
 while j < n:
 sum = i + j
 j += 1
 for k in range(sum):
 print(k)
Big-O:________________________________
2. [10pts] Designer Karoline K. (the “other” Kardashian) is having an exclusive fashion show
where she has N models. If N=5, the models will be numbered [0,1,2,3,4]. Because all the
models are foreign, none of them know each other, so you write the following code to
“introduce” each model to every other model.
def introduce(ModelA, ModelB):
 print(ModelA, “I’d like to introduce you to”, ModelB)
 print(ModelB, “meet”, ModelA)
def fashionShow( listOfModels):
 for modelX in listOfGuests:
 for modelY in listOfGuests:
 introduce(guestX, guestY)
fashionShow( [0,1,2,3,4] )
Notice that the above code introduces the same models to themselves, and also introduces a pair
of model twice (it introduces 0 to 1, and then 1 to 0). This is not exactly the same as a fashion
show with real humans.
Your question: If you assume that a call to the introduce(...) function is your unit of work (i.e.
just like a comparison in a sorting algorithm), what is the Big O complexity class of this
problem? In other words, as the number of models (N) increases, how quickly does the number
of introductions increase?
Answer this question by filling in the following blanks:
If N = 2 the number of Introductions = ___________
If N = 4 the number of Introductions = ___________
If N = 8 the number of Introductions = ___________
So therefore, the complexity class is: O(_________)
Also, if it takes 1 second to introduce each pair of models, how many seconds will you spend
doing introductions if you have 50 models?
Answer: _______________
3. [5pts] Given the following list, list the elements in the order in which binary search accesses
them when searching for the number 4 (if an element is not accessed/compared then don’t list it).
Note: if necessary, the middle of an even sized list will be the lower index number e.g. the
middle of [1, 2, 3, 4] would be 2.
[1, 4, 9, 15, 32, 99, 107]
4. [5pts] Would you use binary search or linear search to search through the following list for
some number? Why?
[17, 3, 81, 62, 19]
5. [18pts] Identify the algorithm being used to sort each of the following lists, and finish sorting
the list showing the new list at each step of the algorithm. Show a complete iteration, not the
small substeps.
Algorithm A
Original List: [7, 3, 4, 2, 1]
First iteration: [3, 4, 2, 1, 7]
Second iteration: [3, 2, 1, 4, 7]
Third iteration: __________________
Fourth iteration (if needed, otherwise leave blank): __________________
Name of Algorithm A: __________________
Big O of Algorithm A: __________________
Algorithm B
Original List: [4, 1, 6, 7, 2]
First iteration: [1, 4, 6, 7, 2]
Second iteration: [1, 2, 6, 7, 4]
Third iteration: __________________
Fourth iteration (if needed, otherwise leave blank): __________________
Name of Algorithm B: __________________
Big O of Algorithm B: __________________
6. [7pts] Given a properly implemented merge sort algorithm and the list [8, 4, 2, 1,
7,11] is it possible for the merge sort algorithm to eventually have to merge the following two
lists? Why or why not?
[8, 4, 2] [1, 7, 11]
7. [20pts] Draw a diagram that illustrates how the merge sort algorithm would sort this list. Draw
the contents of the list after each splitting and merging step of the algorithm. (Note: you can split
the halves either way, but make sure you stay consistent):
[5, -9, 1, 4, 0, -4, 3]
8. [15pts] Here is a sequence of numbers: 3, 8, 2, 6, 0, 11, 1
(a) [5 pts] Illustrate how a bubble-sort would sort the above list of numbers. After each pass,
underline the positions that are guaranteed to be in sorted order. Do all passes, do NOT make
short-cutting optimizations.
(b) [5pts] Illustrate how a selection-sort would sort the above list of numbers. After each pass,
underline the numbers that are guaranteed to be in sorted order.
(c) [5 pts] Illustrate how a merge-sort would sort the above list of numbers.