Big O Cheat Sheet

A quick reference of the time and space costs of all the major data structures and algorithms

Data Structures

	index	search	insert	delete
Array	index	search	insert	delete
Stores things in order. Has quick lookups by index. Full array reference
Dynamic Array	index	search	insert	delete
An array that automatically grows as you add more items. Full dynamic array reference
Linked List	index	search	insert	delete
Also stores things in order. Faster insertions and deletions than arrays, but slower lookups (you have to "walk down" the whole list). Full linked list reference
Queue	index	search	insert	delete
Like the line outside a busy restaurant. "First come, first served." Full queue reference
Stack	index	search	insert	delete
Like a stack of dirty plates in the sink. The first one you take off the top is the last one you put down. Full stack reference
Hash Table	index —	search	insert	delete
Like an array, except instead of indices you can set arbitrary keys for each value. Full hash table reference
Binary Search Tree	index	search	insert	delete
Everything in the left subtree is smaller than the current node, everything in the right subtree is larger. <span complexity="lgn"></span> lookups, but only if the tree is balanced! Full binary search tree reference
Trie	index —	search	insert	delete
Stores a set of strings in a big tree of characters. Good for lookups by prefix. <em>Sometimes</em> saves space. Full trie reference
Heap	index	search	insert	delete
A binary tree where the smallest value is always at the top. Use it to implement a priority queue. Full heap reference
Priority Queue	index	search	insert	delete
A queue where items are ordered by priority. Full priority queue reference
Bloom filter	index —	search	insert	delete —
A constant-space bitmap that lets you quickly check whether or not an item is in a set. Can give false positives. Full bloom filter reference
LRU Cache	index —	search	insert	delete
Lets you quickly identify which item hasn't been used for the longest amount of time. Full lru cache reference

Sorting Algorithms

	worst	best	average	space
Selection Sort	worst	best	average	space
Selection sort works by repeatedly "selecting" the next-smallest element from the unsorted array and moving it to the front. Full selection sort reference
Insertion Sort	worst	best	average	space
Insertion sort works by inserting elements from an unsorted array into a sorted subsection of the array, one item at a time. Full insertion sort reference
Merge Sort	worst	best	average	space
Merge sort works by splitting the input in half, recursively sorting each half, and then merging the sorted halves back together. Full merge sort reference
Quicksort	worst	best	average	space
Quicksort works by recursively dividing the input into two smaller arrays around a pivot item: one half has items smaller than the pivot, the other has larger items. Full quicksort reference
Heapsort	worst	best	average	space
Heapsort is similar to selection sort—we're repeatedly choosing the largest item and moving it to the end of our array. But we use a heap to get the largest item more quickly. Full heapsort reference
Counting Sort	worst	best	average	space
Counting sort works by iterating through the input, counting the number of times each item occurs, and using those counts to compute each item's index in the final, sorted array. Full counting sort reference
Radix Sort	worst	best	average	space
Radix sort works by sorting the input numbers one digit at a time. Full radix sort reference

Big O Cheat Sheet

Data Structures

Sorting Algorithms

Programming interview questions by company:

Programming interview questions by topic: