Algorithms and Problem Solving

Big O describes how work grows with input size:

• O(1): dictionary lookup
• O(log n): binary search
• O(n): one pass over a list
• O(n log n): efficient sorting
• O(n²): two nested passes

def binary_search(values: list[int], target: int) -> int | None:
    low, high = 0, len(values) - 1
    while low <= high:
        middle = (low + high) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return None

Binary search requires sorted values. Recursion needs a base case and must move closer to it. Dynamic programming stores overlapping subproblem results. Use BFS for shortest paths in unweighted graphs and DFS for traversal and cycle detection.

Problem-solving methodCopy Anchor Link

Define input, output and edge cases; write a simple correct solution; measure its complexity; then choose a structure that removes the bottleneck.

ExerciseCopy Anchor Link

Use BFS to find and return the shortest path between two users in a social graph.