What’s one thing you learned? What’s still confusing?
Recursion & Dynamic Programming
Recursion with memoization (@lru_cache) and tabulation. Fibonacci, coin change, LCS.
Linked Lists, Part 1: Singly Linked & Basics
Node class, singly linked list operations (insert, delete, search, in-place reversal), and Floyd's two-pointer technique for cycle detection.
Linked Lists, Part 2: Doubly Linked, Merge & LRU Cache
Doubly linked lists with prev/next pointers, merging two sorted lists, recursive reversal, and a complete LRU cache implementation.
Interactive Labs for This Track
Loop Visualizer
You're a factory robot repeating the same task on an assembly line — watch how loops automate repetitive work
List Slicing
You have a playlist of 50 songs — grab just tracks 10 through 20 with a single slice expression
Sorting Algorithms
You're organizing a library of 10,000 books — which sorting method is fastest?
Ask questions, share insights
| Big O | Name | Example | 1,000 items | 1,000,000 items |
|---|---|---|---|---|
| O(1) | Constant | Dictionary lookup | 1 op | 1 op |
| O(log n) | Logarithmic | Binary search | 10 ops | 20 ops |
| O(n) | Linear | Linear search | 1,000 ops | 1,000,000 ops |
| O(n log n) | Linearithmic | Merge sort | 10,000 ops | 20,000,000 ops |
| O(n^2) | Quadratic | Bubble sort | 1,000,000 ops | 1,000,000,000,000 ops |
import time
def measure_time(func, *args):
"""Measure execution time of a function."""
start = time.time()
result = func(*args)
elapsed = time.time() - start
return result, elapsed
# O(1) -- constant time: dictionary lookup
def dict_lookup(data: dict, key: str):
return data.get(key)
# O(n) -- linear time: search through a list
def linear_search(arr: list, target):
for item in arr:
if item == target:
return True
return False
# O(n^2) -- quadratic time: check all pairs
def has_duplicate_pair(arr: list):
n = len(arr)
for i in range(n):
for j in range(i + 1, n):
if arr[i] == arr[j]:
return True
return False
# Demonstrate scaling
sizes = [1000, 5000, 10000]
for size in sizes:
data = list(range(size))
_, elapsed = measure_time(has_duplicate_pair, data)
print(f"O(n^2) with n={size:>6}: {elapsed:.4f}s")
# Notice: 5x input = ~25x time (quadratic)You double the input size. Sorting takes 4x longer. What's the Big O?
What's the time complexity of binary search on a sorted array of n elements?
Linear search checks every element one by one. Simple but slow for large datasets.
def linear_search(arr: list, target) -> int:
"""Find target in arr. Return index or -1 if not found.
Time complexity: O(n) -- must check each element in the worst case.
Space complexity: O(1) -- no extra memory needed.
"""
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
numbers = [4, 2, 7, 1, 9, 3, 8, 5]
print(linear_search(numbers, 9)) # 4 (index of 9)
print(linear_search(numbers, 6)) # -1 (not found)def binary_search(arr: list, target) -> int:
"""Find target in a SORTED array. Return index or -1 if not found.
Time complexity: O(log n) -- halves the search space each step.
Space complexity: O(1) -- uses only two pointers.
"""
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1 # target is in the right half
else:
right = mid - 1 # target is in the left half
return -1
sorted_numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search(sorted_numbers, 7)) # 3
print(binary_search(sorted_numbers, 12)) # -1import time
# Create a sorted list of 10 million numbers
data = list(range(10_000_000))
target = 9_999_999 # worst case -- near the end
# Linear search
start = time.time()
linear_search(data, target)
linear_time = time.time() - start
# Binary search
start = time.time()
binary_search(data, target)
binary_time = time.time() - start
print(f"Linear search: {linear_time:.4f}s")
print(f"Binary search: {binary_time:.6f}s")
print(f"Binary is {linear_time / binary_time:.0f}x faster")
# Linear search: ~0.5s
# Binary search: ~0.000005s
# Binary is ~100,000x fasterBinary search on 10 million items takes about 23 comparisons (log2(10,000,000) is ~23). Linear search takes up to 10 million comparisons. That is the power of O(log n).
Bubble sort repeatedly swaps adjacent elements that are out of order. Simple to understand but impractical for large datasets.
def bubble_sort(arr: list) -> list:
"""Sort a list using bubble sort.
Time complexity: O(n^2) -- nested loops comparing every pair.
Space complexity: O(1) -- sorts in place.
"""
arr = arr.copy() # do not modify the original
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j] # swap
swapped = True
if not swapped:
break # already sorted -- exit early
return arr
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]def merge_sort(arr: list) -> list:
"""Sort a list using merge sort.
Time complexity: O(n log n) -- divides in half (log n levels), merges all elements per level (n).
Space complexity: O(n) -- needs temporary arrays for merging.
"""
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# Merge
return merge(left, right)
def merge(left: list, right: list) -> list:
"""Merge two sorted lists into one sorted list."""
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Append any remaining elements
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]import time
import random
def compare_sorts(n: int) -> None:
"""Compare bubble sort vs merge sort on random data."""
data = [random.randint(0, n * 10) for _ in range(n)]
start = time.time()
bubble_sort(data)
bubble_time = time.time() - start
start = time.time()
merge_sort(data)
merge_time = time.time() - start
start = time.time()
sorted(data) # Python's built-in Timsort (O(n log n))
builtin_time = time.time() - start
print(f"n={n:>6} | Bubble: {bubble_time:.4f}s | Merge: {merge_time:.4f}s | Built-in: {builtin_time:.6f}s")
compare_sorts(1000)
compare_sorts(5000)
compare_sorts(10000)
# n= 1000 | Bubble: 0.0450s | Merge: 0.0020s | Built-in: 0.000070s
# n= 5000 | Bubble: 1.1200s | Merge: 0.0110s | Built-in: 0.000400s
# n= 10000 | Bubble: 4.5000s | Merge: 0.0230s | Built-in: 0.000900s| Algorithm | Time | Space | When to use |
|---|---|---|---|
| Bubble Sort | O(n^2) | O(1) | Never in practice (educational only) |
| Merge Sort | O(n log n) | O(n) | When you need guaranteed O(n log n) and stability |
Python sorted() | O(n log n) | O(n) | Always in production -- Timsort is highly optimized |
| Binary Search | O(log n) | O(1) | When data is sorted and you need fast lookup |
| Linear Search | O(n) | O(1) | When data is unsorted or very small |
# Binary search is used everywhere in ML:
# 1. Hyperparameter tuning -- binary search for optimal learning rate
def find_best_lr(evaluate_fn, low=1e-5, high=1.0, steps=20):
"""Binary search for the best learning rate."""
for _ in range(steps):
mid = (low + high) / 2
loss_low = evaluate_fn(low + (mid - low) / 3)
loss_high = evaluate_fn(mid + (high - mid) / 3)
if loss_low < loss_high:
high = mid
else:
low = mid
return (low + high) / 2
# 2. K-Nearest Neighbors relies on efficient sorting/searching
def knn_predict(train_data, train_labels, query, k=3):
"""Predict using K-Nearest Neighbors."""
distances = []
for i, point in enumerate(train_data):
dist = sum((a - b) ** 2 for a, b in zip(point, query)) ** 0.5
distances.append((dist, train_labels[i]))
# Sort by distance -- O(n log n)
distances.sort(key=lambda x: x[0])
# Take k nearest
k_nearest = [label for _, label in distances[:k]]
# Return majority vote
from collections import Counter
return Counter(k_nearest).most_common(1)[0][0]
# Example
train_X = [[1, 2], [2, 3], [3, 1], [6, 5], [7, 7], [8, 6]]
train_y = ["A", "A", "A", "B", "B", "B"]
print(knn_predict(train_X, train_y, [5, 5], k=3)) # B
# 3. Python's sorted() is Timsort -- the best general-purpose sort
# Always use it in production instead of implementing your own
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(sorted(data)) # ascending
print(sorted(data, reverse=True)) # descending
print(sorted(data, key=lambda x: -x)) # descending (alt)Tests · Implement search and sort algorithms, then compare performance!
Understanding sorting algorithms builds your algorithm design intuition. Here are all major algorithms, from educational to practical:
# Bubble Sort — repeatedly swap adjacent out-of-order elements
# Time: O(n²) worst/avg, O(n) best (already sorted with flag)
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break # already sorted
return arr
# Selection Sort — find minimum, place at front, repeat
# Time: O(n²) always. Space: O(1)
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# Insertion Sort — build sorted portion one element at a time
# Time: O(n²) worst, O(n) best. Fast for small/nearly-sorted data
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr# Merge Sort — divide and conquer, stable sort
# Time: O(n log n) always. Space: O(n)
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# Quick Sort — partition around pivot, in-place
# Time: O(n log n) avg, O(n²) worst (bad pivot choice). Space: O(log n)
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pivot_idx = partition(arr, low, high)
quick_sort(arr, low, pivot_idx - 1)
quick_sort(arr, pivot_idx + 1, high)
return arr
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1list.sort() and sorted() use Timsort — a hybrid of merge sort and insertion sort:Timsort is designed for real data — file lists, database records, timestamps — which often have sorted "chunks."
# Python's built-in sort is almost always the right choice
arr = [3, 1, 4, 1, 5, 9, 2, 6]
arr.sort() # in-place, O(n log n)
new_arr = sorted(arr) # returns new list
# Sort with a key function
students = [("Alice", 92), ("Bob", 78), ("Charlie", 95)]
students.sort(key=lambda s: s[1]) # sort by grade ascending
students.sort(key=lambda s: s[1], reverse=True) # descending
# Sort complex objects
from dataclasses import dataclass
@dataclass(order=True)
class Task:
priority: int
name: str
tasks = [Task(3, "low"), Task(1, "urgent"), Task(2, "normal")]
tasks.sort() # sorts by priority (dataclass order=True uses field order)| Algorithm | Best | Average | Worst | Space | Stable? | When to use |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Never (educational only) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Never (educational only) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Small or nearly-sorted data |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
sorted() or .sort() in production. Only implement sorting yourself for learning or when you need specific behavior (like an online sort, external sort, or counting sort for integer data).Sometimes you do not need a full sort:
import heapq
# Do not sort to find min/max — O(n) is better than O(n log n)
max_val = max(arr) # O(n)
min_val = min(arr) # O(n)
top_3 = heapq.nlargest(3, arr) # O(n log 3) ≈ O(n)
# Do not sort to check if sorted — O(n)
is_sorted = all(arr[i] <= arr[i+1] for i in range(len(arr)-1))
# Do not sort to find a single element — use binary search on already-sorted data
import bisect
idx = bisect.bisect_left(sorted_arr, target) # O(log n)sorted() which implements Timsortsorted() or .sort() in production, not hand-written sortsWhat does O(n^2) mean in Big O notation?
| Yes |
| When stable + guaranteed O(n log n) needed |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | In-place sort, good cache performance |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | When O(1) extra space required |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Real-world data (Python's default) |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | Small integer range (k is value range) |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes | Integer keys, fixed width |
| Check if sorted | sorted(arr) == arr — O(n log n) + copies | all(arr[i] <= arr[i+1] ...) — O(n) |
| Find one element | Sort then scan — O(n log n) | Linear search O(n) or binary search O(log n) on already-sorted data |
min(), max(), heapq.nlargest(), or bisect when you only need a partial answer. In ML preprocessing pipelines that run on millions of samples, this difference accumulates quickly.