Big-O Notation

Big-O describes how an algorithm's running time or memory grows as input size n grows, ignoring constant factors. Common classes, from fastest to slowest growth:

• O(1) constant — array index lookup
• O(log n) logarithmic — binary search
• O(n) linear — a single loop over the input
• O(n log n) — efficient sorting (merge sort, quicksort)
• O(n²) quadratic — nested loops over the input (e.g. bubble sort)

Arrays

An array stores elements contiguously in memory, giving O(1) access by index but O(n) insertion/deletion in the middle, since later elements must shift.

Stacks, Queues & Linked Lists

A stack is Last-In-First-Out (think: browser back button, function call stack). A queue is First-In-First-Out (think: a print queue, task scheduling). A linked list stores elements as nodes with pointers to the next node — O(1) insertion at the front, but O(n) access by index, unlike an array.

Binary Search Trees

A binary search tree keeps every left child smaller and every right child larger than its parent, giving O(log n) average search, insert, and delete — as long as the tree stays reasonably balanced.

Sorting & Searching

Binary search finds a target in a sorted array in O(log n) by repeatedly halving the search range. Merge sort sorts in O(n log n) by recursively splitting the array in half, sorting each half, and merging the results.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Graphs: BFS & DFS

A graph is a set of nodes connected by edges — modeling anything from social networks to road maps. Breadth-First Search (BFS) explores level by level using a queue, and is ideal for shortest paths in unweighted graphs. Depth-First Search (DFS) explores as far as possible down one path before backtracking, typically using a stack or recursion.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

Hash Tables

A hash table maps keys to values using a hash function to compute an array index, giving average O(1) insert, lookup, and delete. Python's dict and JavaScript's Object/Map are both hash tables under the hood. Collisions (two keys hashing to the same slot) are handled internally via chaining or probing.