🧪 Performance Lab – Test, Analyze, Optimize

As a new engineer on the performance optimization team, your job is to evaluate common algorithms not just for correctness, but for how well they scale. In this assignment, you’ll implement several small functions and assess their performance in terms of time and space complexity.

Each function includes a prompt and space for your analysis.

📁 File: performance_lab.py

This file contains five algorithmic challenges. For each one, you are expected to:

1. Write a working implementation using Python
2. Define your own test cases and verify that your code works
3. Complete the performance analysis block below your function
   • Best-case, worst-case, and average-case time complexity
   • Space complexity
   • Justification of your approach and possible optimizations

Problems

1. Find Most Frequent Element
   Return the value that appears most frequently in a list.

2. Remove Duplicates While Preserving Order
   Remove duplicate values while keeping the original order.

3. Return All Pairs That Sum to Target
   Find all unique pairs of numbers that add up to a given target.

4. Simulate List Resizing
   Model how lists grow dynamically and analyze amortized time complexity.

5. Compute Running Totals
   Return a new list where each item is the sum of all values up to that index.

How to Complete This Lab

• Edit the performance_lab.py file directly.
• Add test cases using print() or assert statements to confirm correctness.
• Fill out the analysis block after each function with your complexity breakdown.
• Use your understanding of core operations (insert, delete, access, traverse) and structure trade-offs from earlier units.

Submission Instructions

When complete:

1. Save and commit your work using Git

2. Push to GitHub using:

   git add .
   git commit -m "Completed performance lab"
   git push

3. Submit your repository link on Learn.