Big-O Notation & Algorithm Time Complexity

An asymptotic upper bound on how an algorithm's running time (or space) grows with input size n, ignoring constants and lower-order terms.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

O(log n), and the data must be sorted. Each step halves the search range.

O(n²) worst and average; O(n) best with an early-exit check on already sorted input. Stable, in place.

O(n²) worst and average; O(n) on nearly sorted data. Stable, in place. Fast for small arrays.

O(n²) in every case, even on sorted input. In place, not stable, but makes only O(n) swaps.

O(n log n) in every case. Needs O(n) extra space. Stable.

O(n log n) average; O(n²) worst case when pivots are consistently bad (e.g. first-element pivot on sorted data). In place, not stable.

O(n log n) in every case, O(1) extra space. Not stable.

Ω(n log n). Counting sort and radix sort beat it because they do not compare elements; counting sort runs in O(n + k) for keys in a range of size k.

Matters when sorting records by one key after another.

O(V + E)

Breadth-first search (BFS).

Single-source shortest paths with nonnegative weights. O((V + E) log V) with a binary heap. Fails with negative edge weights.

Single-source shortest paths that allows negative edge weights and detects negative cycles. O(VE).

All-pairs shortest paths using dynamic programming. O(V³).

Orders the vertices of a directed acyclic graph (DAG) so every edge goes from earlier to later. O(V + E) with DFS or Kahn's algorithm.

Both find a minimum spanning tree. Kruskal sorts edges and adds the cheapest that does not form a cycle (union-find), O(E log E). Prim grows one tree from a start vertex using a priority queue, O(E log V).

O(n²): the inner loop runs n times for each of the n outer iterations.

O(log n): i doubles each time, so the loop runs about log₂ n times.

O(n²): the inner loop runs n + (n-1) + ... + 1 = n(n+1)/2 times in total.

Naive: exponential, about O(2ⁿ), because subproblems are recomputed. Memoized (or bottom-up): O(n).

O(n \log n) by the Master Theorem. This is merge sort's recurrence.

O(\log n) . This is binary search's recurrence.

Overlapping subproblems and optimal substructure. Memoization is top-down caching; tabulation fills a table bottom-up.

Greedy makes the locally best choice and never revisits it; fast but only correct for some problems (e.g. activity selection, Huffman coding). DP considers all subproblem choices.

At least O(depth of recursion), because each active call takes a frame on the call stack.

Averaged over a long sequence of operations, each costs O(1), even though an occasional operation (like a resize) is expensive.