TPS 13: Complexity analysis

Consider the following algorithm, which finds the maximum value in an unordered list. What is its time complexity relative to the size of list, n? Why?

function FindMaxUnordered(list):
    set max to the first value in list
    for value in list:
        if value > max:
            set max to value
    return max

The options are:

• O(1)
• O(log₂(n))
• O(n)
• O(n²)

Now consider this algorithm, which finds the maximum value in an ordered list. What is its time complexity? Why? (Same options as above).

function FindMaxOrdered(list):
    return the last value in list

After we've completed the group share portion, upload a copy of your updated TPS document.