Now that we can analyze the runtime of a function, let’s take a look at the runtime of data structures.
We often search through data structures to find a specific value. In this exercise, you will write a function to find the maximum value of a linked list and you will also analyze the runtime of your function.
The function, find_max
, takes in linked_list
as an input. The function should return the maximum value in the linked list.
Instructions
Fill in the find_max
function such that you return the maximum value in linked_list
by only traversing the linked_list
once.
Use the methods in linkedlist.py and node.py to traverse and get values from the list.
Test cases have been provided for you in order to test your code.
If you only traversed the list once to find the maximum value, what would be the big O runtime of the find_max
function?
Scroll to the bottom of the code and change the value of runtime
to whichever one of these values you think the big O runtime is:
"1"
"N"
"log N"
"N log N"
"N^2"
"2^N"
"N!"