TPS 13: Complexity analysis
- Due Apr 28, 2021 by 10am
- Points 1
- Submitting a file upload
- File Types doc and docx
- Available after Apr 28, 2021 at 9am
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(log2(n))
- O(n)
- O(n2)
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.