Random Questions

Problem 1

O(n log n)

Problem 2

def issorted(numbers):
    for i in range(len(numbers) - 1):
        if numbers[i] > numbers[i + 1]:
            return False
    return True

Problem 3

To determine whether a list is sorted, you must look at each value therein at least once (else you wouldn’t know if it’s in the right place), in which case the running time of issorted is minimally in O(n).

Problem 4

Infinite, as random.shuffle might never (pseudorandomly) return a sorted list.

Problem 5

Ω(n), as the first permutation returned might happen to be sorted, which requires at least n steps to confirm.

Problem 6

O(n! * n), as there are n! ways to permute a list with n numbers, and issorted is in O(n).