Time & Space Complexity
Understand how code scales as input grows.
Visualizing Growth Rates
Small inputs look similar. Large inputs reveal the difference.
How Code Translates to Complexity
O(1) — Constant Time
The number of steps does not depend on the input size. The work is always the same.
Common Cases:
- Accessing an array element by index
- Push/Pop on a Stack
- Get/Set value in a HashMap
O(log n) — Logarithmic Time
The number of steps increases very slowly as input size grows because the input is repeatedly divided.
Common Cases:
- Binary Search on a sorted array
- Searching in a Balanced Binary Search Tree (BST)
- Finding the height of a balanced tree
O(n) — Linear Time
The number of steps grows in direct proportion to the input size.
Common Cases:
- Looping through an array once
- Finding the max/min element in an unsorted array
- Searching in a Linked List
O(n log n) — Log-Linear Time
A combination of linear work with a logarithmic process. Common in efficient sorting.
Common Cases:
- Merge Sort
- Quick Sort (average case)
- Looping through an array while running binary search inside
O(n²) — Quadratic Time
The number of steps grows very quickly as the input size increases. Often involves nested loops.
Common Cases:
- Nested loops over the same input (e.g., `for i in n`, `for j in n`)
- Comparing every pair of elements in a collection
- Bubble Sort, Insertion Sort, Selection Sort
Space Complexity (Memory Usage)
Space = extra memory used by your code
O(1) — Constant Space
The amount of extra memory used does not grow with the input size. Only a few variables are used.
Examples:
- Simple variable declarations (numbers, booleans)
- In-place array modifications (e.g., swapping elements)
- Iterative algorithms like Binary Search
O(n) — Linear Space
The extra memory usage grows in direct proportion to the number of input elements.
Examples:
- Creating a copy of an array or list
- Using a HashMap or HashSet to store all input elements
- A simple recursive function that calls itself n times (without tail optimization)
O(h) — Recursive Space
The extra memory depends on the maximum depth (h) of the recursion stack, not the total number of elements.
Examples:
- Recursive DFS traversal on a tree or graph
- Recursion on a balanced tree (h = log n)
- Recursion on a skewed tree (h = n)