In this section of chapter two, we explore the tradeoffs between lists arrays and lists to determine which data is appropriate for the algorithm. Some of the tradeoffs we read about are finding an element in the array or list with given index i, seeing if a given element is an array or list and if the array is sorted or not. An important concept to take away from this section is that preprocessing allows us to convert between the array and list representations in O(n) time, so we are not limited in which data structure we choose and we can freely jump between which one fits the algorithm best!

Our goal is to complete all four steps of the algorithm in constant time to achieve an efficient run time of O(n²). The data structure we chose to represent the free men is a linked list. We used two arrays (arrays of arrays) that will use O(n²) space to represent the women's preference lists and the men's preference lists. The data structures allow each step of the algorithm to take place in constant time (O(1)). After this section was presented in class it was more clear the tradeoffs between lists and arrays and why we chose certain data structures to represent key elements of the algorithm.

This section did a lot of comparing and contrasting that we went over in detail in class. It was very clear but a lot less interesting because it seemed so repetitive. Readability: 8

In this section we analyze common running times: O(n), O(n log n), O(n²).

• Linear Time- O(n)
  • the run time is at most the size of the input times some constant factor
  • example algorithms that are linear time:
    • computing the maximum
    • merging two sorted lists
• O(n log n) Time