Random Questions
Consider the implementation of sort
, below, which takes a list
as input and returns a sorted version thereof. It calls issorted
, also below, to determine whether those numbers are sorted. It also imports a module, random
, and calls random.shuffle
therein. We’ve included the bottommost line so that you can try out the code in CS50 Sandbox or CS50 IDE, but assume that numbers
could be any list
of size n.
def issorted(numbers):
if sorted(numbers) == numbers:
return True
else:
return False
def sort(numbers):
import random
while not issorted(numbers):
random.shuffle(numbers)
return numbers
print(sort([6, 3, 8, 5, 2, 7, 4, 1]))

(2 points.) According to Python’s documentation, what’s the running time (on average) of
sorted
and, in turn,issorted
? 
(2 points.) Complete the reimplementation of
issorted
below in such a way that its running time is in O(n). If its input, alist
of numbers, each of which you may assume is a uniqueint
, is sorted from smallest to largest, your implementation should returnTrue
; if its input is not sorted so, your implementation should returnFalse
.def issorted(numbers): # TODO

(2 points.) Why can the running time of
issorted
, however implemented, not be in O(1)? 
(2 points.) In the worst case, what might the running time of
sort
itself be?
Consider the reimplementation of sort
, below, which imports a module, itertools
, and calls itertools.permutations
therein. As before, assume that numbers
could be any list
of size n. And assume that this implementation of sort
calls an implementation of issorted
in O(n).
def sort(numbers):
import itertools
for permutation in itertools.permutations(numbers):
if issorted(permutation):
return permutation

(2 points.) What’s a lower bound on the running time of this implementation of
sort
? 
(2 points.) What’s an upper bound on the running time of this implementation of
sort
?