Articles

Big O

A way to talk about how the work grows as the input grows, ignoring constant factors and one laptop's speed.

Constant time

Work that stays flat as the input grows, such as reading one array slot or pushing onto the end.

Linear time

One pass over the input. Twice the data means about twice the work, including a linear search.

Quadratic time

A pass for every element, usually a loop inside a loop. The work grows much faster than one scan.

Logarithmic time

Each step throws away a fraction of what remains, so a million sorted elements is only about twenty comparisons.

Linearithmic time

n times log n. The usual cost of a good sort, and the cost you can sometimes beat when the input is already ordered.

Space for time

Spend extra memory so a later lookup does not scan. The extra space is part of the cost, not a side effect.

Contiguous arrays

Values stored in neighbouring memory, so an index is a jump and an insert in the middle has to move the tail.

Rotating an array

Move the front of a contiguous array to the back. A full turn does nothing, so only the remainder matters.

Two pointers

Two indices on one array, and a rule that moves exactly one of them. Ordered data is what makes the walk linear.

Sliding windows

A subarray you keep as you walk forward, updating the previous slice instead of summing it from scratch.

Hash maps

A key stored with a value so set and get are O(1) on average. The pattern is to remember what you have already seen.

Collisions

Two keys landing in the same slot. A hash map is O(1) on average, not a promise about every single call.

Linked lists

A node holding a value and a next pointer. No random access. Rewiring a pointer you already hold is O(1).

Stacks

Last in, first out. Push and pop touch only the most recent item, both O(1) at the end of an array.

The call stack

The stack the runtime uses for calls. Each call pushes a frame. A return pops it. Recursion is this structure.

Queues

First in, first out. Enqueue at the back, dequeue from the front. Breadth-first search is this rule with vertices as the payload.

Recursion

A function that solves a smaller copy of the same problem, plus a base case that stops the calls.

Binary search

On sorted data, compare with the middle and throw away half. Keep an invariant for where the target can still sit.

Bubble sort

Swap neighbours until the array settles. Easy to remember, and quadratic. A contrast, not the sort to reach for.

Merge sort

Split, sort the halves, then merge two sorted runs with two pointers. O(n log n) time and O(n) extra memory.

Trees

One root, no cycles, and children under each node. Depth here is the number of nodes on the longest path down.

Binary search trees

Everything in the left subtree is smaller, everything in the right is larger. Search is a walk whose cost is the height.

Balanced trees

AVL and red-black trees rotate nodes so the height stays about log n. A skewed tree is just a list drawn vertically.

Heaps

A complete binary tree stored in an array. The minimum or the maximum sits at the root, and updating it is O(log n).

Graphs

Vertices and edges. A tree is a graph with no cycles. A general graph can loop, so a search has to remember where it has been.

Adjacency lists

Each vertex stores the vertices one edge away. One pass over the edge list builds it, and a search asks it for neighbours.

Breadth-first search

A queue walks neighbours, then neighbours of neighbours. On equal edge costs, the first time you arrive is the fewest edges.

Depth-first search

A stack, or recursion, finishes one branch before the others. It answers reachability, not fewest edges.

Dijkstra

Shortest paths when edges have different costs: the breadth-first walk, plus a heap that always extends the cheapest path so far.

Greedy choices

Take the local option you can prove does not block a better future. A rule you can break with one counterexample is not the rule.

Backtracking

Choose, explore, then undo. Depth-first search on decisions you are generating. It explodes unless the space is small or you can prune.

Dynamic programming

The problem is made of smaller problems that overlap. Write the recurrence, then store the answers or fill a table from the base case up.

Memoisation

Before recursing, check whether this state already has an answer. After you compute it, store it so the overlapping call is free.

Tries

A tree of characters. Words that share a prefix share a path from the root, and lookup costs the length of the word.