Big O Notation, Data Structures, and Concurrency

Understanding time complexity, data structures, and concurrency are fundamental skills for any software engineer.

Big O Notation

Big O describes how an algorithm’s performance scales as input grows.

Common Complexities

Time
 ↑
 │         O(2ⁿ)  /
 │              /
 │    O(n²)  /
 │         /
 │  O(n log n)
 │    O(n) ──────
 │  O(log n) ───
 │  O(1) ────────
 └──────────────→ Input size (n)

Rules

1. Drop constants: O(2n) → O(n)
2. Drop lower terms: O(n² + n) → O(n²)
3. Focus on worst case

Data Structures

Arrays / Lists

arr = [10, 20, 30, 40, 50]

Linked Lists

Each node points to the next.

[10] → [20] → [30] → [40] → None

Stacks (LIFO)

stack = []
stack.append(1)   # push
stack.append(2)
stack.pop()       # returns 2

Use cases: Undo operations, function call stack, parsing.

Queues (FIFO)

from collections import deque
queue = deque()
queue.append(1)    # enqueue
queue.popleft()    # dequeue

Use cases: Task scheduling, BFS, message queues.

Hash Maps / Dictionaries

cache = {"user:1": "Alice", "user:2": "Bob"}

How it works: A hash function maps keys to array indices. Collisions are handled by chaining or open addressing.

Trees

Binary Search Tree (BST)

        8
       / \
      3   10
     / \    \
    1   6    14

Balanced Trees (AVL, Red-Black)

Self-balancing → always O(log n) operations.

Heaps

A complete binary tree where parent is always smaller (min-heap) or larger (max-heap).

import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappop(heap)  # returns 1 (smallest)

Use cases: Priority queues, top-K problems.

Graphs

Nodes connected by edges.

# Adjacency list
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
}

Algorithms: BFS (shortest path), DFS (explore all), Dijkstra (weighted paths).

Hashing

Hash Functions

Map data of any size to a fixed-size value:

hash("hello")  # → integer

Properties:

• Same input → same output (deterministic)
• Small change in input → very different output
• Fast to compute

Use cases: Dictionaries, caches, checksums, password storage.

Concurrency

Key Concepts

Python Concurrency

# Threading — good for I/O-bound tasks
import threading

def fetch_data(url):
    response = requests.get(url)
    return response.json()

threads = [threading.Thread(target=fetch_data, args=(url,))
           for url in urls]
for t in threads: t.start()
for t in threads: t.join()

# Multiprocessing — good for CPU-bound tasks
from multiprocessing import Pool

with Pool(4) as p:
    results = p.map(process_item, items)

# Async — good for many I/O operations
import asyncio

async def fetch(url):
    async with aiohttp.ClientSession() as session:
        async with session.get(url) as resp:
            return await resp.json()

results = asyncio.run(asyncio.gather(*[fetch(u) for u in urls]))

When to Use What

Summary