Learn

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

1.

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.

2.

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!"`