Practice analyzing and improving the runtime of programs using Python.

Asymptotic Notation: Python

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.

Finding the Maximum Value in a Linked List

We also often sort data structures in order to organize the values stored in them. In this exercise, you will sort a linked list from smallest value to largest value.

To sort a linked list, we can do the following:
1. Instantiate a new linked list
2. Find the maximum value of our inputted linked list
3. Insert the maximum to the beginning of the new linked list
4. Remove the maximum value from the inputted linked list
5. Repeat steps 2-4 until the head node of the inputted linked list points to `None`
6. Return the new linked list



Sort a Linked List

Dr. Shah is a busy surgeon. He sees so many different patients every day that it's often hard to keep track which patients have which diseases. He decided to store this data in some of the cool data structures he learned about. However, because he never learnt asymptotic notation, he didn't know which data structure would be the fastest. He decided to store his patient data in both a HashMap and a Linked List. 

In the HashMap, he stored the values as key value pairs where the patient's name is the key and the respective patient's disease is the value.

In the Linked List, he made each node a list of two values: the first value is the patient's name and the second value is the patient's disease.

In this exercise, you will select patient data from both the HashMap and Linked List and compare which one is faster.

HashMaps vs. Linked Lists Runtime

Now that you've started learning how to use asymptotic notation to measure the runtime of a function, let's practice with Python!

When analyzing the runtime of a function, it's necessary to check the number of iterations the loop will perform based on the size of the input.

The `count` function on the right takes in a positive integer of size `N`  and returns the number of times it takes to divide `N` by `2` until `N` reaches `1`.

We can analyze the runtime of this function by counting the number of iterations the `while` loop will perform based on the size of the input. 



Analyzing Runtime

In addition to analyzing the runtime of various data structures, it is also important to compare the runtime of different data structures.

In this exercise, we will compare the runtime of retrieving the first value added to a queue to the runtime of retrieving the first value added to a stack.

Kirby Zachariah loves to travel! She's been to six different countries and often forgets the order in which she visited them. However, knowing she has a bad memory, she decided to keep track of the countries she's visited in both a `Queue` and a `Stack`. 

As you can see in the code, the countries have been added both to `my_queue` and `my_stack` in the order they were visited. 
