Algorithm Complexity - Expedition Pace

Welcome back, @name! Darwin here with a new survival skill in programming.

Imagine you're planning an expedition through the jungle. You can choose different routes:

• Route A: Always takes 2 hours, regardless of team size
• Route B: 1 hour per person (team of 10 = 10 hours)
• Route C: Everyone must check equipment with everyone else (10 people = 45 pairs = 45 hours!)

This is an analogy for algorithm complexity - measuring how fast execution time grows depending on data size. This is a crucial skill for every programmer!

What Is Algorithm Complexity?

Computational complexity is a measure describing how fast the execution time or memory usage of an algorithm grows as the input data size increases.

We use Big O notation (read "Big Oh") to describe the "worst case scenario" for an algorithm.

1# Example: Searching for a species in a journal
2
3# Version 1: Simple journal (list)
4species_list = ["Python", "Leo", "Elephas", "Gorilla", ...]  # n elements
5
6def find_species_v1(name):
7    """We must check every element - O(n)"""
8    for species in species_list:  # Potentially n iterations
9        if species == name:
10            return True
11    return False
12
13# Version 2: Dictionary
14species_dict = {"Python": {...}, "Leo": {...}, ...}
15
16def find_species_v2(name):
17    """We only check the hash - O(1)"""
18    return name in species_dict  # Constant time!

Question: Which algorithm is faster for 1,000,000 species?

• List: Potentially checks 1,000,000 elements
• Dictionary: Checks 1 element (thanks to hashing)

Big O Notation - Basics

Big O describes how an algorithm scales as data grows.

Syntax: O(expression), where `n` = input data size

Most Common Complexities (from fastest):

| Notation | Name | Example | Description | |---------|-------|----------|------| | O(1) | Constant | Access dict[key] | Always the same time | | O(log n) | Logarithmic | Binary search | Divides problem in half | | O(n) | Linear | Loop through list | Once per element | | O(n log n) | Linearithmic | Merge/quick sort | Divide and conquer | | O(n²) | Quadratic | Nested loops | Every pair | | O(2ⁿ) | Exponential | All subsets | VERY slow! | | O(n!) | Factorial | All permutations | EXTREMELY slow! |

Safari Analogy

1# O(1) - Constant
2# Like checking a map - always the same amount of time
3def get_camp_location(camp_id):
4    """Dictionary access = O(1)"""
5    camps = {1: "North", 2: "South", 3: "East"}
6    return camps[camp_id]
7
8# O(n) - Linear
9# Like walking a trail - the longer it is, the more time it takes
10def count_species(discovered):
11    """Loop through n elements = O(n)"""
12    count = 0
13    for species in discovered:  # n iterations
14        count += 1
15    return count
16
17# O(n²) - Quadratic
18# Like comparing everyone with everyone on the team
19def find_duplicates(team_members):
20    """Nested loops = O(n²)"""
21    duplicates = []
22    for i, member1 in enumerate(team_members):  # n iterations
23        for j, member2 in enumerate(team_members):  # n iterations each!
24            if i != j and member1 == member2:
25                duplicates.append(member1)
26    return duplicates

O(1) - Constant Complexity

Definition: Execution time does not depend on data size.

1# O(1) operations:
2
3# 1. Accessing a list element by index
4animals = ["Tiger", "Elephant", "Parrot", "Lion"]
5first = animals[0]  # O(1) - direct access
6
7# 2. Accessing a dictionary by key
8catalog = {"Python": "Python", "Leo": "Lion"}
9value = catalog["Python"]  # O(1) - hashing
10
11# 3. Appending to end of list (amortized)
12animals.append("Gorilla")  # O(1)
13
14# 4. Checking length
15length = len(animals)  # O(1) - Python stores the length
16
17# 5. Math operations
18result = 5 + 3  # O(1)
19result = 100 ** 2  # O(1)
20
21# 6. Checking if element in set
22species_set = {"Python", "Leo", "Elephas"}
23exists = "Python" in species_set  # O(1) - hashing!

Safari example:

1class ExpeditionCamp:
2    """Expedition camp with O(1) operations"""
3
4    def __init__(self):
5        self.supplies = {}  # Dictionary for O(1)
6        self.team_size = 0
7
8    def add_supply(self, item, quantity):
9        """O(1) - dictionary access"""
10        self.supplies[item] = quantity
11
12    def get_supply(self, item):
13        """O(1) - dictionary access"""
14        return self.supplies.get(item, 0)
15
16    def get_team_size(self):
17        """O(1) - returning a value"""
18        return self.team_size
19
20# Usage
21camp = ExpeditionCamp()
22camp.add_supply("Water", 100)  # O(1)
23water = camp.get_supply("Water")  # O(1)
24size = camp.get_team_size()  # O(1)

O(n) - Linear Complexity

Definition: Execution time grows proportionally to data size.

1# O(n) operations:
2
3# 1. Loop through all elements
4def print_all_species(species):
5    """O(n) - n iterations"""
6    for s in species:  # n times
7        print(s)
8
9# 2. Searching for element in list
10def find_in_list(animals, target):
11    """O(n) - potentially checks all"""
12    for animal in animals:  # Maximum n checks
13        if animal == target:
14            return True
15    return False
16
17# 3. Summing a list
18def total_distance(distances):
19    """O(n) - traversing the entire list"""
20    total = 0
21    for d in distances:  # n iterations
22        total += d
23    return total
24
25# 4. List comprehension
26squares = [x ** 2 for x in range(n)]  # O(n)
27
28# 5. Copying a list
29original = [1, 2, 3, 4, 5]
30copy = original[:]  # O(n) - copies n elements
31
32# 6. Checking if element in list
33"Python" in animals_list  # O(n) - must check every element

Safari example:

1def analyze_expedition_log(log):
2    """
3    Analyze expedition journal - O(n)
4
5    log: list of entries, each entry = {"day": int, "species": int, "distance": float}
6    """
7    total_species = 0
8    total_distance = 0
9
10    # One loop through n entries = O(n)
11    for entry in log:
12        total_species += entry["species"]
13        total_distance += entry["distance"]
14
15    return {
16        "total_species": total_species,
17        "total_distance": total_distance,
18        "avg_species": total_species / len(log),
19        "avg_distance": total_distance / len(log)
20    }
21
22# Example usage
23log = [
24    {"day": 1, "species": 5, "distance": 12.5},
25    {"day": 2, "species": 3, "distance": 8.0},
26    {"day": 3, "species": 7, "distance": 15.2}
27]
28
29stats = analyze_expedition_log(log)  # O(n) where n = 3
30print(stats)

O(n²) - Quadratic Complexity

Definition: Execution time grows proportionally to the square of data size.

Usually: Nested loops!

1# O(n²) operations:
2
3# 1. Nested loops - classic example
4def print_all_pairs(animals):
5    """O(n²) - every pair"""
6    for animal1 in animals:  # n iterations
7        for animal2 in animals:  # n iterations for each of n
8            print(f"{animal1} and {animal2}")
9    # Total: n * n = n² pairs
10
11# 2. Bubble sort - simple sorting
12def bubble_sort(arr):
13    """O(n²) - in the worst case"""
14    n = len(arr)
15    for i in range(n):  # n iterations
16        for j in range(n - 1):  # ~n iterations
17            if arr[j] > arr[j + 1]:
18                arr[j], arr[j + 1] = arr[j + 1], arr[j]
19    return arr
20
21# 3. Finding duplicates (naive)
22def find_duplicates(items):
23    """O(n²) - compares every pair"""
24    duplicates = []
25    for i in range(len(items)):  # n times
26        for j in range(i + 1, len(items)):  # ~n/2 times
27            if items[i] == items[j]:
28                duplicates.append(items[i])
29    return duplicates

Why is O(n²) a problem?

1import time
2
3def slow_comparison(n):
4    """O(n²) - comparisons"""
5    count = 0
6    for i in range(n):
7        for j in range(n):
8            count += 1
9    return count
10
11# Test
12for size in [10, 100, 1000]:
13    start = time.time()
14    result = slow_comparison(size)
15    elapsed = time.time() - start
16    print(f"n={size:4d}: {result:7d} operations, {elapsed:.6f}s")
17
18# Results:
19# n=  10:     100 operations, 0.000010s
20# n= 100:   10000 operations, 0.000850s  (100x more data = 100x longer)
21# n=1000: 1000000 operations, 0.085000s  (1000x more = 1,000,000x longer!)

Safari example - comparing all pairs of locations:

1def calculate_all_distances(locations):
2    """
3    O(n²) - calculates distance between every pair of locations
4
5    locations: list of tuples (x, y) coordinates
6    """
7    import math
8
9    distances = {}
10    n = len(locations)
11
12    # Nested loops = O(n²)
13    for i in range(n):  # n iterations
14        for j in range(i + 1, n):  # ~n/2 iterations each
15            loc1 = locations[i]
16            loc2 = locations[j]
17
18            # Calculate Euclidean distance
19            dist = math.sqrt((loc1[0] - loc2[0])**2 + (loc1[1] - loc2[1])**2)
20
21            distances[f"{i}-{j}"] = dist
22
23    return distances
24
25# Example
26locations = [(0, 0), (3, 4), (6, 8), (1, 1)]
27distances = calculate_all_distances(locations)  # O(4²) = O(16) operations
28print(distances)
29# {'0-1': 5.0, '0-2': 10.0, '0-3': 1.41..., '1-2': 5.0, '1-3': 3.16..., '2-3': 7.28...}

O(log n) - Logarithmic Complexity

Definition: Time grows logarithmically - at each step we divide the problem in half.

Classic example: Binary search

1def binary_search(sorted_list, target):
2    """
3    O(log n) - we divide the range in half at each step
4
5    sorted_list: sorted list
6    target: value to find
7    """
8    left = 0
9    right = len(sorted_list) - 1
10
11    while left <= right:
12        mid = (left + right) // 2  # Middle of range
13
14        if sorted_list[mid] == target:
15            return mid  # Found!
16        elif sorted_list[mid] < target:
17            left = mid + 1  # Search right half
18        else:
19            right = mid - 1  # Search left half
20
21    return -1  # Not found
22
23# Example
24species = ["Elephas", "Gorilla", "Leo", "Loxodonta", "Panthera", "Python"]
25index = binary_search(species, "Leo")  # O(log 6) = ~2.5 comparisons
26print(f"Found at position: {index}")  # 2
27
28# Comparison:
29# Linear search (O(n)): Maximum 6 comparisons
30# Binary search (O(log n)): Maximum 3 comparisons (log2 6 ≈ 2.58)

Why is O(log n) fast?

1# For n = 1,000,000 elements:
2# - O(n): 1,000,000 operations
3# - O(log n): ~20 operations (log2 1,000,000 ≈ 19.93)
4
5# That's 50,000x faster!
6
7import math
8
9for n in [10, 100, 1000, 10000, 1000000]:
10    log_n = math.log2(n)
11    print(f"n={n:>7d}: O(n)={n:>7d}, O(log n)={log_n:>5.2f}, ratio={n/log_n:>8.0f}x")
12
13# Results:
14# n=     10: O(n)=     10, O(log n)= 3.32, ratio=       3x
15# n=    100: O(n)=    100, O(log n)= 6.64, ratio=      15x
16# n=   1000: O(n)=   1000, O(log n)= 9.97, ratio=     100x
17# n=  10000: O(n)=  10000, O(log n)=13.29, ratio=     752x
18# n=1000000: O(n)=1000000, O(log n)=19.93, ratio=   50169x

O(n log n) - Linearithmic

Definition: Time grows as n multiplied by log n.

Classic example: Efficient sorting algorithms (merge sort, quick sort, heap sort)

1def merge_sort(arr):
2    """
3    O(n log n) - divide and conquer
4
5    How it works:
6    1. Divide the array in half (log n levels)
7    2. Merge sorted halves (n operations at each level)
8    Total: O(n log n)
9    """
10    if len(arr) <= 1:
11        return arr
12
13    # Divide in half
14    mid = len(arr) // 2
15    left = merge_sort(arr[:mid])  # Recursion - log n levels
16    right = merge_sort(arr[mid:])
17
18    # Merge sorted halves - O(n)
19    return merge(left, right)
20
21def merge(left, right):
22    """Merge two sorted lists - O(n)"""
23    result = []
24    i = j = 0
25
26    while i < len(left) and j < len(right):
27        if left[i] < right[j]:
28            result.append(left[i])
29            i += 1
30        else:
31            result.append(right[j])
32            j += 1
33
34    result.extend(left[i:])
35    result.extend(right[j:])
36    return result
37
38# Python's built-in sort() uses Timsort - also O(n log n)
39animals = ["Tiger", "Elephant", "Parrot", "Lion", "Gorilla"]
40sorted_animals = sorted(animals)  # O(n log n)

Complexity Comparison - Practical Numbers

| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) | |---|------|----------|------|------------|-------|-------| | 10 | 1 | 3 | 10 | 30 | 100 | 1,024 | | 100 | 1 | 7 | 100 | 700 | 10,000 | 1.27×10³⁰ | | 1,000 | 1 | 10 | 1,000 | 10,000 | 1,000,000 | ∞ | | 10,000 | 1 | 13 | 10,000 | 130,000 | 100,000,000 | ∞ |

Conclusions:

• O(1), O(log n), O(n), O(n log n) - good for large data
• O(n²) - ok for small data (<1000 elements)
• O(2ⁿ), O(n!) - avoid - only for very small data!

Complexity of Python Operations

Lists

| Operation | Complexity | Example | |----------|-----------|----------| | Access | O(1) | `arr[5]` | | Append | O(1) | `arr.append(x)` | | Insert | O(n) | `arr.insert(0, x)` | | Delete | O(n) | `arr.remove(x)` | | Search | O(n) | `x in arr` | | Slicing | O(k) | `arr[1:5]` (k=slice length) | | Copy | O(n) | `arr[:]` | | Sort | O(n log n) | `arr.sort()` |

Dictionaries

| Operation | Complexity | Example | |----------|-----------|----------| | Access | O(1) | `dict[key]` | | Insert | O(1) | `dict[key] = val` | | Delete | O(1) | `del dict[key]` | | Search (key) | O(1) | `key in dict` | | Search (value) | O(n) | `val in dict.values()` |

Sets

| Operation | Complexity | Example | |----------|-----------|----------| | Add | O(1) | `s.add(x)` | | Remove | O(1) | `s.remove(x)` | | Search | O(1) | `x in s` | | Union | O(n+m) | `s1 | s2` | | Intersection | O(min(n,m)) | `s1 & s2` |

Practical Example - Optimization

1# PROBLEM: Find duplicates in list of discoveries
2
3discoveries = ["Python", "Leo", "Elephas", "Python", "Gorilla", "Leo", "Python"]
4
5# ❌ Wrong - O(n²)
6def find_duplicates_slow(items):
7    """O(n²) - nested loops"""
8    duplicates = []
9    for i in range(len(items)):
10        for j in range(i + 1, len(items)):
11            if items[i] == items[j] and items[i] not in duplicates:
12                duplicates.append(items[i])
13    return duplicates
14
15# ✅ Good - O(n)
16def find_duplicates_fast(items):
17    """O(n) - single pass with set"""
18    seen = set()  # O(1) operations
19    duplicates = set()
20
21    for item in items:  # O(n)
22        if item in seen:  # O(1) check in set!
23            duplicates.add(item)
24        else:
25            seen.add(item)  # O(1)
26
27    return list(duplicates)
28
29# Performance comparison
30import time
31
32# For 1000 elements:
33large_list = ["Item_" + str(i % 100) for i in range(1000)]
34
35start = time.time()
36result1 = find_duplicates_slow(large_list)  # O(n²) = O(1,000,000)
37time_slow = time.time() - start
38
39start = time.time()
40result2 = find_duplicates_fast(large_list)  # O(n) = O(1,000)
41time_fast = time.time() - start
42
43print(f"Slow: {time_slow:.4f}s")  # ~0.5s
44print(f"Fast: {time_fast:.4f}s")  # ~0.0005s
45print(f"Speedup: {time_slow/time_fast:.0f}x")  # ~1000x faster!

Space Complexity - Memory Complexity

Besides time, memory is also important!

1# O(1) space - constant memory
2def sum_list(arr):
3    """O(1) space - only one variable"""
4    total = 0  # One variable regardless of n
5    for num in arr:
6        total += num
7    return total
8
9# O(n) space - linear memory
10def copy_list(arr):
11    """O(n) space - copies entire list"""
12    return arr[:]  # New list of size n
13
14# O(n) space - list in memory
15def squares_list(n):
16    """O(n) space - creates a list"""
17    return [x ** 2 for x in range(n)]  # List of n elements
18
19# O(1) space - generator!
20def squares_gen(n):
21    """O(1) space - generates one at a time"""
22    return (x ** 2 for x in range(n))  # Doesn't create a list!

Practical Exercise

Write 3 versions of a function checking whether a list contains duplicates:

1. O(n²) version: Nested loops
2. O(n log n) version: Sort + check neighbors
3. O(n) version: Using set

Measure time for different data sizes (10, 100, 1000, 10000).

Summary

In this lesson you learned:

• ✅ What computational complexity is
• ✅ Big O notation and its significance
• ✅ The most common complexities: O(1), O(log n), O(n), O(n log n), O(n²)
• ✅ How to analyze code for performance
• ✅ Complexity of operations in Python (list, dict, set)
• ✅ How to optimize algorithms
• ✅ The difference between time and space complexity

Checkpoint

Before moving on:

• [ ] You understand Big O notation
• [ ] You can determine the complexity of simple loops
• [ ] You know why dict is faster than list for searching
• [ ] You understand why nested loops are O(n²)
• [ ] You know the difference between O(n) and O(log n)
• [ ] You can optimize code by choosing better data structures

Golden rule: "Premature optimization is the root of all evil" - first write working code, then optimize if needed!

In the next lesson Darwin will show you sorting algorithms - how to classify discoveries! 🔢📊