🔍 Advanced Comparative Analysis — Choosing Optimally

Master the deep tradeoffs and design patterns for selecting ideal data structures.

🎯 Comprehensive Complexity Comparison

*O(1) with index access

**O(1) append, O(n) insert at position

💡 Memory Overhead Analysis

import sys

# Measure actual memory usage
lst = list(range(1000))
dct = {i: i for i in range(1000)}
st = set(range(1000))
tpl = tuple(range(1000))

print(f"List:       {sys.getsizeof(lst) / 1024:.1f} KB")    # ~8.3 KB
print(f"Dict:       {sys.getsizeof(dct) / 1024:.1f} KB")    # ~37.2 KB
print(f"Set:        {sys.getsizeof(st) / 1024:.1f} KB")     # ~36.7 KB
print(f"Tuple:      {sys.getsizeof(tpl) / 1024:.1f} KB")    # ~8.0 KB

# Per-element memory
print(f"\nPer-element (1000 items):")
print(f"List:   {sys.getsizeof(lst) / 1000:.1f} bytes")
print(f"Dict:   {sys.getsizeof(dct) / 1000:.1f} bytes")
print(f"Set:    {sys.getsizeof(st) / 1000:.1f} bytes")
print(f"Tuple:  {sys.getsizeof(tpl) / 1000:.1f} bytes")

# Actual element sizes
print(f"\nElement sizes:")
print(f"Integer object:  {sys.getsizeof(1)} bytes")
print(f"String object:   {sys.getsizeof('x')} bytes")

🎨 Algorithm-Specific Selection

Problem 1: Finding Duplicates

# Approach A: Nested loops with list - O(n²)
def has_duplicates_slow(data):
    for i in range(len(data)):
        for j in range(i+1, len(data)):
            if data[i] == data[j]:
                return True
    return False

# Approach B: Set-based - O(n)
def has_duplicates_fast(data):
    seen = set()
    for item in data:
        if item in seen:
            return True
        seen.add(item)
    return False

# Benchmark
import timeit
data = list(range(10000))
slow = timeit.timeit(lambda: has_duplicates_slow(data[:1000]), number=10)
fast = timeit.timeit(lambda: has_duplicates_fast(data), number=10)
print(f"Slow: {slow:.3f}s, Fast: {fast:.3f}s, Speedup: {slow/fast:.0f}x")

Problem 2: Frequent Lookups with Updates

# Scenario: Maintain user session data with frequent lookups

# Wrong choice: List of tuples O(n) per lookup
sessions_list = [
    ("user1", {"token": "abc", "expires": 3600}),
    ("user2", {"token": "def", "expires": 3600})
]

# Must iterate to find user - O(n)
for user_id, session in sessions_list:
    if user_id == "user1":
        token = session["token"]
        break

# Right choice: Dictionary O(1) lookup
sessions_dict = {
    "user1": {"token": "abc", "expires": 3600},
    "user2": {"token": "def", "expires": 3600}
}

# Instant access
token = sessions_dict["user1"]["token"]

# Performance on 10,000 sessions
import timeit
sessions = [(f"user{i}", {"token": f"tok{i}"}) for i in range(10000)]
sessions_d = {f"user{i}": {"token": f"tok{i}"} for i in range(10000)}

list_time = timeit.timeit(
    lambda: next((s[1] for s in sessions if s[0] == "user9999"), None),
    number=100
)

dict_time = timeit.timeit(
    lambda: sessions_d.get("user9999"),
    number=100
)

print(f"List lookup: {list_time:.4f}s")  # ~0.05s
print(f"Dict lookup: {dict_time:.6f}s")  # ~0.00001s
print(f"Speedup: {list_time/dict_time:.0f}x")  # 5000x faster!

📊 Space-Time Tradeoff Matrix

🔑 Key Takeaways

• ✅ List for sequential access; O(n) lookup penalty

• ✅ Dict for fast lookups; 4-5x memory overhead

• ✅ Set when membership checks dominate; unique values

• ✅ Tuple for minimal memory; immutability required

• ✅ Benchmark real code before optimizing

Ready to practice? Challenges | Quiz