Time Complexity of Common Operations — Python, Java, JavaScript, C++
A per-language time-complexity reference for the data-structure operations coding interviews actually test — dict / HashMap / Map / unordered_map, list / ArrayList / Array / vector, and the deque, heap, and sorted-structure lines side by side.
The lookup reference for a single question: "how fast is <operation> on <data structure> in <language>?" Same operations across four languages, in tables you can screenshot. When you need the algorithm-level view — sorting complexities, graph traversals, language gotchas as prose — see the Big-O cheat sheet. This post is the tighter, comparison-focused sibling.
How to read the tables
- Amortised (*) means averaged over a sequence of operations.
list.appendis amortised O(1) even though a single call might resize the backing array in O(n); over any long sequence, the average is O(1). - Worst case in parentheses where a common failure mode diverges from the amortised bound.
HashMap.getin Java is amortised O(1) but O(log n) worst-case per bucket post-Java-8 (tree-bucket fallback). - n = element count unless otherwise noted. k is a scale variable that isn't n (key length, distinct values, batch size).
Hash map — dict / HashMap / Map / unordered_map
| Operation | Python dict | Java HashMap | JavaScript Map | C++ unordered_map |
|---|---|---|---|---|
get(k) / d[k] | O(1)* | O(1)* (O(log n) worst) | O(1)* | O(1)* (O(n) worst) |
put(k, v) / d[k] = v | O(1)* | O(1)* | O(1)* | O(1)* |
delete(k) / del d[k] | O(1)* | O(1)* | O(1)* | O(1)* |
contains(k) / k in d | O(1)* | O(1)* | O(1)* | O(1)* |
| Iteration | O(n) | O(n + capacity) | O(n) | O(n + capacity) |
| Copy | O(n) | O(n) | O(n) | O(n) |
Per-language notes:
- Python: insertion-ordered since 3.7.
dict.get(k, default)never raises.dict.pop(k, default)combines get + delete. - Java: post-Java-8, buckets that fill with collisions convert to red-black trees — worst case per bucket becomes O(log n) instead of O(n).
LinkedHashMappreserves insertion order at a small constant-factor cost. - JavaScript:
Mapis spec'd as sublinear. Keys can be any type (unlikeObject[k]which coerces to string). Iteration is insertion-ordered. - C++:
unordered_mapamortised O(1) but O(n) worst case on adversarial hashing (each bucket a linked list, no tree fallback). Rehashes when load factor exceedsmax_load_factor(default 1.0). For guaranteed O(log n), usestd::map(balanced BST).
Hash set — set / HashSet / Set / unordered_set
| Operation | Python set | Java HashSet | JavaScript Set | C++ unordered_set |
|---|---|---|---|---|
add(x) | O(1)* | O(1)* | O(1)* | O(1)* |
remove(x) | O(1)* | O(1)* | O(1)* | O(1)* |
contains(x) / x in s | O(1)* | O(1)* | O(1)* | O(1)* |
Union a | b | O(len(a) + len(b)) | O(a + b) | manual, O(a + b) | O(a + b) |
Intersection a & b | O(min(a, b)) | via retainAll — O(a + b) | manual, O(a + b) | O(a + b) |
Difference a - b | O(len(a)) | via removeAll — O(a + b) | manual, O(a + b) | O(a + b) |
| Iteration | O(n) | O(n) | O(n) | O(n) |
Same worst-case caveats as the hash-map row — collision-heavy inputs degrade to O(n) per operation in Python/C++, O(log n) in Java-8+.
Dynamic array — list / ArrayList / Array / vector
| Operation | Python list | Java ArrayList | JavaScript Array | C++ vector |
|---|---|---|---|---|
[i] access | O(1) | O(1) | O(1) | O(1) |
[i] = x assign | O(1) | O(1) | O(1) | O(1) |
append(x) / push(x) | O(1)* | O(1)* | O(1)* | O(1)* |
pop() (end) | O(1) | O(1) | O(1) | O(1) |
pop(0) / shift() | O(n) | O(n) | O(n) | O(n) |
insert(0, x) / unshift(x) | O(n) | O(n) | O(n) | O(n) |
insert(i, x) (mid) | O(n) | O(n) | O(n) | O(n) |
remove(x) (by value) | O(n) | O(n) | O(n) | O(n) |
contains(x) / x in a | O(n) | O(n) | O(n) | O(n) |
sort() | O(n log n) Timsort | O(n log n) Timsort/dual-pivot QS† | O(n log n) TimSort | O(n log n) IntroSort |
| Slice / subarray copy | O(k) | O(k) | O(k) | O(k) |
| Reverse | O(n) | O(n) | O(n) | O(n) |
Concatenate a + b | O(a + b) | O(a + b) | O(a + b) | O(a + b) |
† Java: Arrays.sort(int[]) uses dual-pivot Quicksort — O(n²) worst case. Arrays.sort(Object[]) and Collections.sort use Timsort — O(n log n) worst case.
The bolded rows are the interview-classic traps. Every one of them turns an "O(n) solution" into an accidental O(n²):
- Using
list.pop(0)in a BFS queue → per-op O(n), overall O(V²). Reach forcollections.deque. - Membership testing with
x in listinside a loop → O(n · loop_iterations). Convert to asetfirst. - Building a string by repeated concat with
+=→ O(n²) becausestris immutable. Collect +join.
Deque — double-ended queue
| Operation | Python deque | Java ArrayDeque | JavaScript (no built-in) | C++ deque |
|---|---|---|---|---|
append(x) right | O(1) | O(1) | Array.push — O(1)* | O(1) |
appendleft(x) | O(1) | O(1) | Array.unshift — O(n) | O(1) |
pop() right | O(1) | O(1) | Array.pop — O(1) | O(1) |
popleft() | O(1) | O(1) | Array.shift — O(n) | O(1) |
Random access [i] | O(n) | O(1) | O(1) | O(1) |
| Iteration | O(n) | O(n) | O(n) | O(n) |
Notes:
- Python
deque: O(1) at both ends, O(n) for arbitrary indexing. If you need both O(1) ends and random access, use two lists or roll a fixed-size ring buffer. - Java
ArrayDeque: prefer over the legacyStack(synchronised, slow) andLinkedList(poor cache locality) whenever you need stack or queue semantics. - JavaScript: no native deque.
Arraygives O(1) at the right only; usingunshift/shiftfor the left is O(n). For BFS, useArraywith a head-index counter, or a small custom class. - C++
std::deque: O(1) at both ends and O(1) random access — it's not a linked list, it's a segmented array. Worse cache locality thanstd::vectorbut strictly more flexible.
Binary heap — priority queue
| Operation | Python heapq | Java PriorityQueue | JavaScript (no built-in) | C++ priority_queue |
|---|---|---|---|---|
| Push | O(log n) | O(log n) | — | O(log n) |
| Pop | O(log n) | O(log n) | — | O(log n) |
| Peek (top) | O(1) | O(1) | — | O(1) |
| Build from array | O(n) via heapify | O(n) via constructor | — | O(n) via constructor |
nlargest(k, iter) | O(n log k) | manual | — | manual |
| Delete arbitrary | O(n) | O(n) | — | O(n) |
| Increase / decrease key | O(n) (Python) / O(n) (default) | O(n) | — | O(n) |
Notes:
- Python
heapq: min-heap only. For a max-heap, push negated values (-num) or(-priority, item).heapq.heapify(list)is O(n), not O(n log n) — a common interview claim to get right. - Java
PriorityQueue: min-heap by default. PassComparator.reverseOrder()for a max-heap, or a custom comparator for tuples/objects. - JavaScript: no built-in heap. Common workaround is a small class over an array; libraries like
js-priority-queueexist. Rolling your own is a fifteen-line exercise. - C++
priority_queue: max-heap by default. For min-heap:priority_queue<int, vector<int>, greater<int>>.std::make_heapon a container is O(n).
For "decrease key" (Dijkstra's classic need), the standard-library heaps don't support it directly in O(log n). Workaround: push the new (smaller) priority and let the old entry expire on pop with a stale-check. That's what most interview Dijkstra solutions do.
Sorted structures — balanced BST equivalents
Not all languages have one built in. When they're missing, you either roll a balanced BST yourself (rare in interviews) or reach for a sorted-array-plus-binary-search combination.
| Operation | Python (no built-in) | Java TreeMap / TreeSet | JavaScript (no built-in) | C++ std::map / std::set |
|---|---|---|---|---|
| Insert | via sortedcontainers.SortedList: O(log n) | O(log n) | manual, O(log n) if rolled | O(log n) |
| Delete | O(log n) | O(log n) | manual | O(log n) |
| Lookup by key | O(log n) | O(log n) | manual | O(log n) |
| Floor / ceiling / next / prev | O(log n) | O(log n) via floorKey etc. | — | O(log n) via lower_bound etc. |
| Kth smallest | O(log n) with augmented tree; O(k) with iteration | O(k) with iteration | — | O(k) with iteration |
| In-order iteration | O(n) | O(n) | — | O(n) |
Python competitive-coding standard: from sortedcontainers import SortedList, SortedDict, SortedSet. Non-stdlib but pip-installable and widely used. LeetCode ships it in their Python runtime.
Linked list
| Operation | Python (no built-in — use deque) | Java LinkedList | JavaScript (no built-in) | C++ std::list (doubly) |
|---|---|---|---|---|
Access [i] | — | O(n) | — | O(n) |
| Insert at head | — | O(1) | — | O(1) |
| Insert at tail | — | O(1) | — | O(1) |
| Insert at arbitrary position (with iterator) | — | O(1) | — | O(1) |
| Delete (with node pointer) | — | O(1) | — | O(1) |
| Search | — | O(n) | — | O(n) |
Python doesn't ship a linked list — collections.deque is a segmented ring buffer that covers most linked-list use cases with better cache locality. Java's LinkedList is almost always worse in practice than ArrayList or ArrayDeque; use it only when you specifically need O(1) mid-list splicing via an iterator.
String
Strings are their own topic because they're immutable in Python, Java, and JavaScript. Every "modification" allocates a new string.
| Operation | Python str | Java String | JavaScript string | C++ std::string |
|---|---|---|---|---|
[i] access | O(1) | O(1) | O(1) | O(1) |
| Length | O(1) | O(1) | O(1) | O(1) |
Concatenate a + b | O(a + b) | O(a + b) | O(a + b)† | O(a + b) |
Concat in loop with += | O(n²) | O(n²) | O(n)† modern engines | O(n²) if reallocating |
| Slice / substring | O(k) | O(k) post-Java-7 | O(k) | O(k) |
find / indexOf (naïve) | O(n · m) | O(n · m) | O(n · m) | O(n · m) |
find (with KMP-like optimisations) | implementation-dependent | O(n) in some cases | — | — |
replace (all) | O(n) | O(n) | O(n) | O(n) |
split | O(n) | O(n) | O(n) | O(n) |
join(list, sep) | O(total_length) | O(total_length) | O(total_length) | O(total_length) |
† JavaScript engines use rope structures for string concatenation, so a + b is often O(1) internally. But relying on this optimisation across engines is fragile; the safe rule is still "collect into an array and .join('')".
The safe rule in every language: never build a string via repeated concat inside a loop. Collect chunks in a list/array/StringBuilder, then join in one call.
- Python:
"".join(pieces) - Java:
StringBuilderwith.append(), then.toString() - JavaScript:
array.push(chunk); ...; array.join("") - C++:
std::stringwith.reserve()up front, then.append()— orstd::ostringstream
Common surprises
Grouped by "which O(n) trap have I probably fallen into":
"Why is my BFS O(V²)?" — You used list.pop(0) (Python), Array.shift() (JavaScript), or a LinkedList.pollFirst() where ArrayDeque.pollFirst() was expected. See the BFS vs DFS post.
"Why is my sliding-window O(n · k)?" — You wrote if x in window where window is a list, not a set or dict. x in list is O(n).
"Why is my string-building solution TLE-ing?" — Repeated s = s + t inside a loop is O(n²) in Python and Java. Use "".join(pieces) or StringBuilder.
"Why is my Dijkstra slower than the analyst-expected bound?" — Python's heapq lacks decrease-key. Push duplicate entries with fresher priorities and skip stale ones on pop. That's the amortised O((V + E) log V) implementation — the theoretical O((V + E) log V) with true decrease-key needs a Fibonacci heap and is rarely worth writing.
"Why does my Java HashMap have such a stable worst case?" — Post-Java-8 tree buckets. When collisions in one bucket exceed a threshold (TREEIFY_THRESHOLD = 8), the bucket becomes a red-black tree — O(log n) per bucket, not O(n).
How to argue in an interview
Interviewers grade the argument, not just the answer. The three-line script that works in every language:
- Name the operation and structure by their concrete type. "Reading
nums[i]on a Python list is O(1)." Not "array indexing is O(1)" — you'll get pressed on whether it's a Python list or a NumPy array or a linked-list-in-disguise. - State whether the bound is amortised or worst-case. "Amortised O(1) for
dict.get— hash-map get averages O(1), even if a single collision-heavy lookup could be O(n)." - If the worst case matters for the problem, defend it. "Assuming Python's default hash function isn't adversarially chosen, this is O(n) overall. If the interviewer expects worst-case bounds, I'd downgrade to O(n²)."
Interviewers rarely push all the way into hash-collision theory. They want to see you know the number and the caveat.
Cross-references
- The Big-O cheat sheet covers the algorithm-level view (sorting, graph, string algorithms, specialised structures) with prose per-language gotchas.
- The Python interview cheat sheet covers the idioms and standard-library shortcuts that turn the raw complexity numbers into readable code.
- Every pattern post rests on some line of the tables above. The sliding-window pattern needs O(1) hash-map ops. The two-pointer pattern needs O(n log n) sort. The binary-search template is one row: O(log n) on a sorted structure. The monotonic-stack pattern uses O(1) dynamic-array append/pop. The backtracking template uses the same O(1) list append/pop plus an O(k) list snapshot per recorded solution. The BFS-vs-DFS decision post hinges on the deque row.
The tables aren't wallpaper. They're the invariants every pattern is cashing in on.