# 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]))
``````
1. (2 points.) According to Python’s documentation, what’s the running time (on average) of `sorted` and, in turn, `issorted`?

2. (2 points.) Complete the reimplementation of `issorted` below in such a way that its running time is in O(n). If its input, a `list` of numbers, each of which you may assume is a unique `int`, is sorted from smallest to largest, your implementation should return `True`; if its input is not sorted so, your implementation should return `False`.

`````` def issorted(numbers):
# TODO
``````
3. (2 points.) Why can the running time of `issorted`, however implemented, not be in O(1)?

4. (2 points.) In the worst case, what might the running time of `sort` itself be?

Consider the re-implementation 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
``````
1. (2 points.) What’s a lower bound on the running time of this implementation of `sort`?

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