The cost table for common data structures

Complexity analysis Junior Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Pick the fix

You need fast lookups by key and also the smallest key at any time, with inserts and deletes. Which structure fits best?

OptionsA balanced search tree (or a sorted container)A hash map aloneA binary heap alone

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A A balanced search tree (or a sorted container)

Right: O(log n) lookup, insert, delete and min.

Only an ordered structure keeps every one of those operations logarithmic.

Why not the others?

B A hash map alone. It gives O(1) lookups but finding the minimum is O(n).
C A binary heap alone. Finding or deleting an arbitrary key is O(n).

30-second answer

Arrays: O(1) index, O(n) insert in the middle. Hash maps and sets: O(1) average insert, delete and lookup, no order. Binary heaps: O(1) peek at the minimum, O(log n) push and pop. Balanced search trees: O(log n) insert, delete, lookup and ordered queries. Linked lists: O(1) insert or delete at a known node, O(n) to find it.

Practise saying it · 60 s. No recording, just a timer

Recite the main costs for the common structures.

Say your answer out loud, then check which of these points you covered:

Hash: O(1) average
Heap: O(log n) push/pop
Balanced tree: O(log n) ordered

Deep dive

Pick the structure from the operations you need most, then quote its costs.

Python has no built-in balanced tree; bisect on a sorted list gives O(log n) search with O(n) insert.

Kotlin on the JVM has TreeMap and TreeSet (red-black trees) for ordered O(log n) operations.

Structure	Find	Insert	Delete	Min or ordered query
Array or list	O(n)	O(1) at end, O(n) in middle	O(n)	O(n)
Hash map or set	O(1) average	O(1) average	O(1) average	O(n)
Binary heap	O(n)	O(log n)	O(log n) for the min	O(1) for the min
Balanced search tree	O(log n)	O(log n)	O(log n)	O(log n)
Linked list	O(n)	O(1) at a known node	O(1) at a known node	O(n)

Common mistakes

Using a heap when you need to find or delete arbitrary items.
Assuming hash maps keep insertion order in every language (Python dicts do; a plain Java HashMap does not).

Senior take & follow-ups

Choose the structure by listing the operations first. It turns guessing into reasoning.

Follow-up questions

Think of your answer first, then open the hint.

What gives O(1) LRU caching?
Show hint
A hash map plus a doubly linked list (or Python's OrderedDict).
What supports 'k-th smallest' with updates?
Show hint
An order-statistics tree or a Fenwick tree over ranks.

What each operation costs: Bubble Sort · Merge Sort · Binary Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.