Objective

We want to compare various implementations of dynamic order statistics:

1. With a sorted list
2. With a BST without the size attribute
3. As seen in class

Requirements

Write Python programs (not notebooks) that:

• Implement the requested solutions
• Run a set of tests that allow us to understand the advantages and disadvantages of the different implementations
• Carry out and analyze appropriate experiments
• Write a report (in LaTeX) describing what has been done (as indicated in the instructions on the course Moodle page)

⚠ Attention
The list must be implemented using pointer-based linked structures and not Python’s built-in list data structure.