Time and Space Complexity – Cheat Sheet

What is time complexity?

Time complexity is a measure of how the running time of an algorithm increases as the input size increases. It indicates the number of steps the algorithm takes based on the input. Since every computer takes a different time to perform computation, we need a standard mechanism to measure the speed of computation, which is given by time complexity. It measures how fast the number of operations increases as inputs get bigger.

What is space complexity?

Space complexity is the amount of memory or space the algorithm takes to run as a function of input size. It includes:

fixed parts -> which are the constants, program instructions, and variables
variable part -> which includes memory of data structures used, stacks, function calls, and temporary variables.

Common Time Complexities

Use case	Complexity
constant	O(1)
binary search, divide and conquer	O(log n)
traversing array/ list	O(n)
merge sort, quick sort	O(n log n)
nested loops, bubble sort	O(n² )
matrix multiplication	O(n³ )
recursive fibonnacci, subset generation	O(2ⁿ )
travelling salesman	O(n!)

Data Structure Operations:

Data Structure	Insert	Search	Delete
Array (Sorted)	O(n)	O(log n)	O(n)
Array (Unsorted)	O(1)	O(n)	O(n)
Linked List	O(1) (at head)	O(n)	O(n)
Stack/Queue	O(1)	O(1)	O(1)
Hash Table	O(1) (avg)	O(1) (avg)	O(1) (avg)
BST (balanced)	O(log n)	O(log n)	O(log n)
BST (skewed)	O(n)	O(n)	O(n)
Heap	O(log n)	O(1)	O(log n)

Sorting Algorithms:

Algorithm	Best Case Complexity	Worst Case Complexity	Average Case Complexity	Space Complexity
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)

Loop Patterns:

Use Case	Complexity
Simple Loop	O(n)
Multiply Step	O(log n)
Nested Loops	O(n²)
Triangular Nested Loops	O(n²)
Logarithmic Inner Loop	O(n log n)