Why does a hash table give O(1) lookup?

A hash function maps a key directly to a bucket index, so lookups, inserts and deletes are average O(1). The worst case is O(n) when many keys collide into the same bucket, which good hashing and resizing keep rare. Hash tables have no inherent ordering or index access.

When is an array better than a linked list?

Use an array when you need random access by index (O(1)) or cache-friendly iteration. Use a linked list when you frequently insert or delete in the middle and already hold the node, since that is O(1) versus O(n) for an array's element shifting.

Why can a binary search tree degrade to O(n)?

A plain BST degrades when inserts arrive in sorted order, forming a linked-list-like chain of height n. Self-balancing trees such as AVL and red-black rebalance on each operation to guarantee O(log n) height, keeping all operations logarithmic in the worst case.

What does O(V+E) mean for graphs?

V is the number of vertices and E the number of edges. A full traversal like BFS or DFS visits every vertex once and every edge once, giving O(V + E) on an adjacency-list graph. An adjacency matrix instead costs O(V²) to scan because it stores a cell for every possible edge.

Does this reference send my searches anywhere?

No. Filtering happens entirely in your browser. Nothing you type is uploaded, logged or stored.

Data Structure Complexity Reference

Email me this result

Get this tool's output sent to your inbox, plus one useful tool a week. No spam, unsubscribe any time.

Picking a structure by its dominant operation

The right data structure depends on which operation you do most: random access, searching, or inserting and deleting. This reference lists the Big-O time complexity for each of those operations across the common structures — arrays, linked lists, hash tables, trees, heaps and graphs — plus their space cost. Search by keyword and highlight the operation you care about.

How it works

Each structure trades operations against one another. The headline complexities:

Array          access O(1)   search O(n)   insert/delete O(n)
Linked list    access O(n)   search O(n)   insert/delete O(1)*  (*with node ref)
Hash table     search/insert/delete O(1) avg, O(n) worst, no order
Balanced BST   all O(log n) worst-case guaranteed
Binary heap    peek O(1), push/pop O(log n)
Graph (list)   traversal O(V+E),  Graph (matrix) edge lookup O(1), traversal O(V²)

Average-case figures assume good conditions: a low hash load factor, a balanced tree, a reasonable distribution. Structures that can degrade — hash tables and unbalanced BSTs — are marked so you can plan for the worst case.

Tips and notes

Dynamic-array append is amortised O(1) but occasionally O(n) when the backing buffer resizes — fine for most uses, watch it in latency-critical paths.
Hash tables win for key lookup but give no ordering; use a balanced tree (or a B-tree on disk) when you also need sorted traversal or range queries.
Heaps give O(1) access to the min or max but are not searchable in log time — reach for them for priority queues, not membership tests.
Choose adjacency lists for sparse graphs (O(V+E) space) and matrices for dense graphs needing O(1) edge checks.