Measure efficiency with Big-O, then use searching, sorting, hash maps, stacks, linked lists, trees, graphs and dynamic programming in Python.

Data Structures & Algorithms

## Why it matters

Two programs can give the same answer and still behave very differently. One finishes instantly on a list of a million items; the other takes hours. The difference is rarely the computer or the language. It is how much work the algorithm does as the input grows. Big-O notation is the shared vocabulary developers, data scientists and interviewers use to talk about that growth, and it tells you which solution will still work when your data gets ten or a thousand times bigger.

## The core idea: count steps, not seconds

Seconds depend on the machine, the language and what else is running. Instead, we count the basic steps an algorithm takes (a comparison, an addition, a lookup) as a function of the input size, called `n`. Then we keep only the part that dominates when `n` is large and drop constant factors.

- A loop that does 3 steps per item does `3n` steps. That is **O(n)**.
- `3n + 100` is still **O(n)**: for large `n` the `+ 100` stops mattering.
- `n^2 + n` is **O(n^2)**: the square term wins.

Big-O describes the **worst case** unless someone says otherwise, and it describes **shape**, not speed. An O(n) loop in slow code can lose to an O(n^2) loop on tiny inputs, but as `n` grows, the better shape always wins.

## The common classes

| Big-O | Name | Example | n = 1,000 |
|---|---|---|---|
| O(1) | constant | read `items[0]`, look up a dict key | 1 step |
| O(log n) | logarithmic | binary search in a sorted list | about 10 steps |
| O(n) | linear | find the max of a list | 1,000 steps |
| O(n log n) | linearithmic | merge sort, Python's `sorted` | about 10,000 steps |
| O(n^2) | quadratic | compare every pair | 1,000,000 steps |

`log n` here means log base 2: how many times you can halve `n` before you reach 1. For a billion items that is only about 30.

## Worked example: finding duplicates

Here is a direct way to check whether a list has a repeated value:

```python
def has_duplicates_slow(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False
```

For each item, it compares against every later item. With `n` items that is `(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2` comparisons in the worst case (no duplicates). For 4 items that is 6 comparisons; for 1,000 items, 499,500; for 100,000 items, about 5 billion. That is **O(n^2)**.

Now use a set, which can check membership in roughly constant time:

```python
def has_duplicates_fast(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False
```

One pass, one set lookup and one insert per item: **O(n)** time. The trade-off is memory: the set can hold up to `n` items, so it uses **O(n) extra space**. Trading memory for time like this is one of the most common moves in algorithm design.

## Reading Big-O from code

A few rules cover most everyday code:

1. **Sequential steps add.** A loop over `n` followed by another loop over `n` is `O(n + n) = O(n)`.
2. **Nested loops multiply.** A loop over `n` inside a loop over `n` is `O(n * n) = O(n^2)`.
3. **Halving gives a log.** A loop that cuts the remaining work in half each time is `O(log n)`.
4. **Know your built-ins.** `x in some_list` is O(n) (it scans), but `x in some_set` and `d[key]` are O(1) on average. `some_list.insert(0, x)` is O(n) because every element shifts. Sorting with `sorted()` is O(n log n).

```python
def total_and_max(nums):
    total = sum(nums)      # O(n)
    biggest = max(nums)    # O(n)
    return total, biggest  # overall O(n)
```

## Common mistakes

- **Hidden loops.** `if x in my_list:` inside a `for` loop over the same list looks like one loop but is O(n^2).
- **Keeping constants.** Writing O(2n) or O(n/2). Both are just O(n).
- **Confusing best and worst case.** Linear search can find the target on the first try, but its Big-O is still O(n).
- **Forgetting space.** A fast solution that builds a huge dictionary may not fit in memory.
- **Optimising too early.** For 20 items, the clearest code is usually best. Big-O matters when inputs grow.

## Quick recap

- Big-O describes how work grows with input size `n`, ignoring constants and smaller terms.
- From best to worst: O(1), O(log n), O(n), O(n log n), O(n^2).
- Nested loops multiply, sequential loops add, halving gives log n.
- A set or dict often turns an O(n^2) search into O(n), at the cost of extra memory.

## Try it

Open the **Do** tab. You will write an O(n) duplicate check with a set and a function that counts how many comparisons the nested-loop version makes, so you can see the quadratic growth in numbers.


Describe how an algorithm's work grows with its input, and compare O(1), O(log n), O(n) and O(n^2) code.

Big-O notation

Computational Complexity - CS50 Shorts

Big-O Notation in 100 Seconds

## Why it matters

Searching is everywhere: finding a user by ID, a word in a dictionary, the first log line after a timestamp, the right version that introduced a bug (`git bisect` is binary search). Knowing when you can do better than "look at everything" is one of the most practical skills in this course, and binary search is a classic interview question because it is short but easy to get subtly wrong.

## Linear search

Linear search checks each item in turn until it finds the target or runs out of items.

```python
def linear_search(items, target):
    for i, value in enumerate(items):
        if value == target:
            return i
    return -1
```

- Works on **any** list, sorted or not.
- Worst case: the target is last or missing, so it looks at all `n` items. **O(n)**.
- Python's `items.index(x)` and `x in items` are linear searches under the hood.

For a short list, or a list you search only once, linear search is the right tool. Sorting first costs O(n log n), which is more than one O(n) scan.

## Binary search

If the list is **sorted**, you can do far better. Look at the middle item:

- If it is the target, you are done.
- If the target is bigger, it can only be in the right half.
- If the target is smaller, it can only be in the left half.

Each comparison throws away half of what is left. A million items need at most about 20 comparisons. That is **O(log n)**.

```python
def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1      # target is to the right of mid
        else:
            high = mid - 1     # target is to the left of mid
    return -1
```

`low` and `high` mark the part of the list that could still hold the target. The loop runs while that range is not empty (`low <= high`).

## Worked example

Search for `23` in `[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]` (10 items, indexes 0–9).

| step | low | high | mid | items[mid] | action |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 16 | 16 < 23, so low = 5 |
| 2 | 5 | 9 | 7 | 56 | 56 > 23, so high = 6 |
| 3 | 5 | 6 | 5 | 23 | found, return 5 |

Three looks instead of six. Now search for `20`: after step 2 we check index 5 (23 > 20, high = 4). Now `low = 5 > high = 4`, the range is empty, and we return `-1`.

## Edge cases to test

Binary search bugs hide in the edges, so always try:

- an **empty** list (`high` starts at -1, the loop never runs, return -1),
- a **one-item** list, target present and absent,
- the **first** and **last** items,
- a target **smaller** than everything and **larger** than everything,
- a target that would sit **between** two items.

## Common mistakes

- **Using `<` instead of `<=`.** With `while low < high`, a one-item range is never checked, so the search misses targets.
- **Writing `low = mid` or `high = mid`.** The range may stop shrinking and the loop runs forever. Move past `mid` with `+ 1` / `- 1`.
- **Searching an unsorted list.** Binary search gives wrong answers, not errors, on unsorted data.
- **Slicing.** `binary_search(items[mid:], target)` copies half the list each time, which is O(n) work per step and also breaks the returned index. Move `low` and `high` instead.

## In the standard library

Python's `bisect` module does binary search for you. `bisect.bisect_left(items, x)` returns the index where `x` would be inserted to keep the list sorted. If that index is inside the list and `items[i] == x`, you found it. Writing your own once is how you learn to trust and debug the library version.

```python
import bisect
items = [2, 5, 8, 12, 16]
i = bisect.bisect_left(items, 12)   # 3
```

## Quick recap

- Linear search: any list, O(n).
- Binary search: sorted list only, halves the range each step, O(log n).
- Keep `low`/`high` bounds, loop while `low <= high`, move past `mid`.
- Test empty, one item, first, last, and missing values.

## Try it

In the **Do** tab, write both searches. One check counts how many items your binary search looks at in a 500,000-item list, so a disguised linear scan will not pass.


Search an unsorted list step by step, then halve a sorted list each time with binary search.

Linear and binary search

Linear Search - CS50 Shorts

Binary Search - CS50 Shorts

## Why it matters

Sorted data makes many problems easy: binary search, finding duplicates, merging records, ranking. In real code you will almost always call `sorted()` or `.sort()`, which are fast and well tested. Writing two sorts yourself is still worth it: it is the clearest way to see the difference between O(n^2) and O(n log n), and the ideas (insert into a sorted part, split and merge) come back in many other algorithms.

## Insertion sort

Think of sorting a hand of playing cards. You keep the left part of your hand sorted and take one new card at a time, sliding it left until it sits in the right place.

```python
def insertion_sort(items):
    result = list(items)              # copy so we do not change the input
    for i in range(1, len(result)):
        current = result[i]
        j = i - 1
        while j >= 0 and result[j] > current:
            result[j + 1] = result[j]  # shift the bigger item right
            j -= 1
        result[j + 1] = current        # drop current into the gap
    return result
```

Trace `[5, 2, 4, 1]`:

| i | current | after this pass |
|---|---|---|
| 1 | 2 | `[2, 5, 4, 1]` |
| 2 | 4 | `[2, 4, 5, 1]` |
| 3 | 1 | `[1, 2, 4, 5]` |

**Cost.** In the worst case (reverse-sorted input) each new item shifts past every item before it: `1 + 2 + ... + (n-1)`, about `n^2 / 2` steps, so **O(n^2)**. On a list that is already sorted, the inner loop never runs and it is O(n). That makes insertion sort good for small or nearly-sorted lists; Python's built-in sort uses it on short runs.

## Merge sort

Merge sort is **divide and conquer**:

1. If the list has 0 or 1 items, it is already sorted (the base case).
2. Split it into two halves.
3. Sort each half (by calling merge sort on it).
4. **Merge** the two sorted halves into one sorted list.

The key piece is `merge`. Both inputs are sorted, so the smallest remaining item is always at the front of one of them.

```python
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:])    # one side may have leftovers
    result.extend(right[j:])
    return result


def merge_sort(items):
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))
```

Trace `merge([2, 5, 9], [1, 6])`: compare 2 and 1, take 1; compare 2 and 6, take 2; 5 and 6, take 5; 9 and 6, take 6; right is empty, so add the leftover 9. Result `[1, 2, 5, 6, 9]`.

**Cost.** Each level of splitting does O(n) work in total to merge, and halving gives about `log n` levels. So merge sort is **O(n log n)** in every case, best and worst. For 100,000 items that is about 1.7 million steps versus about 5 billion for insertion sort's worst case. The cost is O(n) extra memory for the merged lists.

Using `<=` (not `<`) in `merge` keeps equal items in their original order. That property is called **stability**, and it matters when you sort records by one field after another.

## What Python does

`sorted()` uses Timsort, a hybrid of merge sort and insertion sort. It is O(n log n), stable and very fast on real data, which often has sorted runs. Use it in production code. You can sort by a key:

```python
people = [("Ada", 36), ("Linus", 21), ("Grace", 45)]
by_age = sorted(people, key=lambda p: p[1])
```

## Common mistakes

- **Forgetting leftovers in merge.** When one side runs out, the rest of the other side must be added.
- **No base case.** `merge_sort` on a one-item list must return immediately or it recurses forever.
- **Changing the input by accident.** If the caller did not ask for an in-place sort, work on a copy.
- **Assuming O(n^2) is always bad.** For 10 items, insertion sort is fine and simple.

## Quick recap

- Insertion sort: grow a sorted prefix one item at a time. O(n^2) worst, O(n) on sorted input.
- Merge sort: split, sort halves, merge. O(n log n) always, O(n) extra memory, stable with `<=`.
- In real code, call `sorted()`.

## Try it

In the **Do** tab, `merge_sort` is written for you. Write `merge` and `insertion_sort`; the checks compare your results with `sorted()` on random lists, duplicates, negatives and edge cases.


Implement insertion sort and merge sort, and see why one is O(n^2) and the other O(n log n).

Sorting algorithms

Insertion Sort - CS50 Shorts

Merge Sort - CS50 Shorts

Describe how code slows as data grows with Big-O notation, then implement linear and binary search, insertion sort and merge sort.