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, 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
```
(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 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

(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?