Learn data structures by doing
Watch an operation step by step, then try it with your own values.
Explore topics
Time & Space Complexity
Use asymptotic notation to describe how an algorithm’s work or memory grows as its input gets larger.
Asymptotic notation
n is the input size, such as the number of array values, list nodes, or expression tokens. For time, choose an operation to count. For space, count memory slots or other storage used while the algorithm runs.
O(g(n))Upper bound- For large inputs, the work grows no faster than a constant times g(n).
Ω(g(n))Lower bound- For large inputs, the work grows at least as fast as a constant times g(n).
Θ(g(n))Tight bound- Both bounds match. The work grows at the same rate as g(n), up to constant factors.
For example, 3n + 7 is Θ(n). It is also O(n²), but that upper bound is looser. Best, average, and worst tell you which inputs you’re counting. Any of those cases can have an upper, lower, or tight bound.
Common growth rates
O(1)- Constant work. Reading an array slot by index takes the same number of steps as the array grows.
O(log n)- One extra halving when the input doubles. Binary search repeatedly halves a sorted search range.
O(n)- One pass. Scanning twice as many elements can take twice as much work.
O(n log n)- About n work per level across log n levels, as in merge sort.
O(n²)- Two full nested scans. Doubling both loop lengths makes about four times as much work.
Algorithm & Data Structure Complexity Matrix
Compare the three time bounds for each operation or algorithm at the same input size.
- Best
- Least work at size n. Linear search can find the target first.
- Average
- Expected work under a stated input distribution. With a uniformly placed match, linear search checks about half the array.
- Worst
- Most work at size n. Linear search checks every value when the target is absent.
Scroll the table sideways to see all columns.
| Operation or algorithm | Best time | Average time | Worst time | Extra space | Stable | In-place |
|---|
- Extra space
- Count working storage such as Merge Sort’s temporary buffer. Total space also includes the input. A separate output can add memory, as in Infix → Postfix.
- Stable
- A stable sort keeps equal keys in their original order. If
2acame before2b, it still comes first after sorting. - In-place
- This table uses the constant-extra-space definition for sorting. Our Quick Sort partitions inside the array and can still hold
O(n)pending ranges in the worst case. - Amortized
- Spread the total cost across a sequence of operations. One dequeue using two stacks can take
O(n), while the amortized cost isO(1).
A dash marks a property that does not apply, or an average that needs an input distribution.
Follow the animation
Example only · your data stays the same
CurrentNew / changedRemovedCheck your understanding
Show answer
Illustrative addresses and fixed-width values. Runtime layouts and allocation policies vary by language and implementation.
Build a linked list from the beginning
HEAD is a pointer, not a node. Create it, allocate a node, then connect them.
- 1 · Create HEAD = NULL
- 2 · Create the first node
- 3 · Connect HEAD to it
- 4 · Extend & save
Click empty space to create a node. Drag NEXT to another node.