I
DSA · Ironclad
// REFERENCE

The Big-O cheat sheet

Time and space complexity for every structure and sort you'll meet in an interview — colour-coded so the expensive ones jump out. Scrub the chart to feel how each class explodes as n grows.

Big-O Growth
02004006008001000n (input size)04008001.2koperationsO(1)
O(1)O(log n)O(n)O(n log n)O(n²)O(2ⁿ)
›
Big-O notation describes how the operation count grows as input size n grows. We are about to plot six complexity classes on the same axes — watch how they diverge as n increases.
01/09
y-axis capped at 1 200 ops for readability

The complexity classes, fastest to slowest

Big-O
Name
Shows up in
O(1)
Constant
array index, hash lookup
O(log n)
Logarithmic
binary search, balanced-BST ops
O(n)
Linear
scan an array, linked-list search
O(n log n)
Linearithmic
merge sort, heap sort
O(n²)
Quadratic
nested loops, bubble sort
O(2ⁿ)
Exponential
naive recursive fibonacci, subsets

Data structure operations

average-case unless noted · *heap access = peek min/max

Structure
Access
Search
Insert
Delete
Space
Array
O(1)
O(n)
O(n)
O(n)
O(n)
Stack
O(n)
O(n)
O(1)
O(1)
O(n)
Queue
O(n)
O(n)
O(1)
O(1)
O(n)
Linked List
O(n)
O(n)
O(1)
O(1)
O(n)
Hash Table
—
O(1)
O(1)
O(1)
O(n)
Binary Search Tree
O(log n)
O(log n)
O(log n)
O(log n)
O(n)
Balanced BST (AVL/RB)
O(log n)
O(log n)
O(log n)
O(log n)
O(n)
Heap
O(1)*
O(n)
O(log n)
O(log n)
O(n)
Trie
—
O(L)
O(L)
O(L)
O(N·L)

Sorting algorithms

Algorithm
Best
Average
Worst
Space
Stable
Bubble Sort
O(n)
O(n^2)
O(n^2)
O(1)
yes
Selection Sort
O(n^2)
O(n^2)
O(n^2)
O(1)
no
Insertion Sort
O(n)
O(n^2)
O(n^2)
O(1)
yes
Merge Sort
O(n log n)
O(n log n)
O(n log n)
O(n)
yes
Quick Sort
O(n log n)
O(n log n)
O(n^2)
O(log n)
no
Heap Sort
O(n log n)
O(n log n)
O(n log n)
O(1)
no

Frequently asked

What is the time complexity of common data structures?+

Arrays give O(1) access but O(n) search and insertion in the middle. Hash tables give O(1) average insert, search, and delete. Balanced binary search trees give O(log n) for search, insert, and delete while keeping elements ordered. Heaps give O(1) access to the min or max and O(log n) insert and extract.

Which sorting algorithm is the fastest?+

For general data, the O(n log n) comparison sorts — merge sort, quicksort, and heapsort — are the fastest you can do with comparisons. Quicksort is usually fastest in practice due to cache behaviour, but its worst case is O(n²); merge sort guarantees O(n log n) and is stable; heapsort guarantees O(n log n) in O(1) extra space.

Why do we drop constants and lower-order terms in Big-O?+

Big-O describes how an algorithm scales as the input grows toward infinity, not its exact running time. As n grows, the highest-order term dominates and constants become irrelevant — O(2n + 100) and O(n) describe the same linear growth, so both are written O(n).

▸ Learn Big-O from scratchBrowse data structures