Skip to content
All articles

Big-O and the Data Structures Every Engineer Should Know

Dean Jain

Dean Jain

Senior Staff Software Engineer · Enterprise AI, Data & Cloud Architect

· 6 min read

AlgorithmsData StructuresBig-OFundamentals
---
config:
  theme: neutral
  fontSize: 16
---
flowchart LR
    A["O(1)<br/>constant"]:::good --> B["O(log n)<br/>logarithmic"]:::good
    B --> C["O(n)<br/>linear"]:::server
    C --> D["O(n log n)<br/>linearithmic"]:::obs
    D --> E["O(n²)<br/>quadratic"]:::warn
    E --> F["O(2ⁿ) / O(n!)<br/>exponential / factorial"]:::danger
    classDef good fill:#FFFFFF,stroke:#333333,stroke-width:1px,color:#111111
    classDef server fill:#F0F0F0,stroke:#333333,stroke-width:1px,color:#111111
    classDef obs fill:#DAE8FC,stroke:#333333,stroke-width:1px,color:#111111
    classDef warn fill:#DCDCDC,stroke:#333333,stroke-width:1px,color:#111111
    classDef danger fill:#E8E8E8,stroke:#333333,stroke-width:1px,color:#111111

Figure 1: Big-O complexity classes, best to worst how an algorithm's cost grows as the input grows.

Big-O notation gets taught as interview trivia, which buries its real value. It doesn’t tell you how fast an algorithm is it tells you how its cost grows as the input grows. That’s the question that actually matters in production, because the thing that works fine on 1,000 rows and falls over on 10 million is almost always an algorithm or data structure whose Big-O you didn’t think about. And the lever you pull is usually the data structure: the same operation is O(1) on one and O(n) on another. Here’s the working knowledge every engineer should carry.

Summary

  • Big-O measures scaling, not speed. O(1) is flat, O(log n) barely grows, O(n²) and worse explode. Aim for the left side of the chart on anything that grows.
  • The data structure sets the Big-O of your operations. Array = O(1) random access but O(n) insert/delete; linked list = O(1) insert but O(n) access; hash map = O(1) lookup; tree = O(log n) and ordered.
  • Hash vs tree is the recurring choice: hash for fast unordered lookup, tree (BST/red-black) when you need sorted order or ranges.
  • Trees power storage. B-trees/B+ trees minimize disk reads (databases, indexes); the right tree keeps operations O(log n).
  • Know the specialized few: Bloom filters (probabilistic membership), skip lists (searchable linked lists) they’re behind Cassandra, Redis, and more.

1. Big-O is about growth

Big-O describes how an algorithm’s runtime (or space) changes with input size n it abstracts away constants and hardware to capture the shape of the growth. The classes, from delightful to dangerous:

  • O(1) constant cost doesn’t change with input (is a number odd or even). The dream.
  • O(log n) logarithmic barely grows even as data explodes (binary search on a sorted array). Excellent.
  • O(n) linear cost tracks input (find the max in an unsorted array). Fine.
  • O(n log n) linearithmic the best you can do for general sorting (mergesort). Acceptable.
  • O(n²) quadratic nested loops over the data (bubble sort, naive duplicate-finding). Trouble at scale.
  • O(2ⁿ) exponential / O(n!) factorial all subsets, all permutations. Tractable only for tiny n.

The practical reading: the difference between O(n) and O(n²) is the difference between a feature that scales and one that times out the moment your data grows. You don’t need to compute Big-O for every line you need to notice when you’ve written a nested loop over a large collection, or when a structure forces O(n) where O(1) was available. That noticing is the whole skill, and the data structure is usually how you fix it.

2. The core structures and their trade-offs

Each structure makes some operations cheap and others expensive picking the right one is choosing your Big-O:

---
config:
  theme: neutral
  fontSize: 16
---
flowchart TD
    NEED["What do you need cheap?"]:::gov
    NEED -->|"random access by index"|ARR["Array<br/>O(1) access, O(n) insert/delete"]:::server
    NEED -->|"frequent insert/delete"|LL["Linked list<br/>O(1) insert, O(n) access"]:::obs
    NEED -->|"fast key lookup"|MAP["Hash map / set<br/>O(1) lookup, unordered"]:::gate
    NEED -->|"sorted order / ranges"|TREE["Tree (BST / red-black)<br/>O(log n), ordered"]:::good
    classDef gov fill:#FFFFFF,stroke:#333333,stroke-width:1px,color:#111111
    classDef server fill:#F0F0F0,stroke:#333333,stroke-width:1px,color:#111111
    classDef obs fill:#DAE8FC,stroke:#333333,stroke-width:1px,color:#111111
    classDef gate fill:#DCDCDC,stroke:#333333,stroke-width:1px,color:#111111
    classDef good fill:#E8E8E8,stroke:#333333,stroke-width:1px,color:#111111

Figure 2: Choose by the operation you need cheap and accept the cost on the others.

  • Array / ArrayList O(1) random access by computing an offset (base + size × index). But inserts/deletes need shifting/copying (O(n)). Great for fixed-ish data you read a lot and rarely mutate.
  • Linked list O(1) insert/delete at a known position (just relink), but O(n) access since you traverse to reach an element. Great for frequent structural changes.
  • Hash map / set O(1) average lookup by key, unordered, handling collisions with chaining or secondary hashing. The default when you just need “is it there?” or “get by key.” (In concurrent code, reach for ConcurrentHashMap, not the legacy synchronized Hashtable.)
  • Tree (BST, red-black) O(log n) operations and ordered traversal. A red-black tree (a self-balancing BST) backs Java’s TreeMap/TreeSet. Use a tree when you need sorted order, range queries, or “next greater” exactly what a hash map can’t give you.

The recurring decision is hash vs tree: hash wins for raw unordered lookup speed; tree wins the moment you need order. And arrays vs linked lists is access-vs-mutation. Naming the operation you need cheap picks the structure and pins your Big-O.

3. Graphs and traversal

For connected data a network of entities and relationships you reach for graphs: vertices (entities) and edges (relationships), which can be directed, weighted, cyclic. Two representations trade space for query speed: an adjacency matrix (2-D array fast edge lookup, more space) or an adjacency list (array of edge lists less space, O(n) to check an edge). And two ways to traverse, distinguished by the structure that tracks pending nodes: breadth-first uses a queue (FIFO), depth-first uses a stack (LIFO). That queue-vs-stack distinction is one of those small facts that unlocks a whole category of problems.

4. The structures that power your database

Some structures aren’t everyday tools but are everywhere underneath and knowing them demystifies how databases actually work:

---
config:
  theme: neutral
  fontSize: 16
---
flowchart TD
    BT["B-tree / B+ tree<br/>O(log n), minimizes disk reads"]:::server --> U1["DB indexes, filesystems"]:::obs
    BF["Bloom filter<br/>probabilistic membership"]:::gate --> U2["Cassandra/HBase SSTable checks"]:::obs
    SL["Skip list<br/>searchable linked list, O(log n)"]:::good --> U3["Redis sorted sets"]:::obs
    classDef server fill:#FFFFFF,stroke:#333333,stroke-width:1px,color:#111111
    classDef gate fill:#F0F0F0,stroke:#333333,stroke-width:1px,color:#111111
    classDef good fill:#DAE8FC,stroke:#333333,stroke-width:1px,color:#111111
    classDef obs fill:#DCDCDC,stroke:#333333,stroke-width:1px,color:#111111

Figure 3: Specialized structures and what they power B-trees in indexes, Bloom filters in SSTable lookups, skip lists in Redis.

  • B-tree / B+ tree self-balancing trees designed to minimize disk reads. They’re “fat” (many keys per node, node size ≈ disk block), so the tree stays shallow and most operations need only O(log n) disk accesses far fewer than a binary tree. A B+ tree keeps all data in linked leaf nodes for fast ordered/range scans. This is why your database index is a B+ tree.
  • Bloom filter a space-efficient probabilistic structure that answers “is this possibly in the set, or definitely not?” false positives possible, false negatives never. Cassandra and HBase use them to skip SSTables/StoreFiles that definitely lack a row, avoiding pointless disk reads.
  • Skip list a linked list with extra “express lane” nodes that let you binary-search it, giving O(log n) search/insert/delete. It backs Redis sorted sets a simpler-to-implement alternative to balanced trees.

You won’t hand-code these often, but recognizing them turns “the database is magic” into “the index is a B+ tree, the membership check is a Bloom filter” which is exactly the understanding that lets you reason about performance.

Why it matters: Big-O and data structures aren’t academic gatekeeping they’re the difference between code that scales and code that mysteriously dies at 10× the data. You rarely invent an algorithm; you choose a data structure, and that choice sets the Big-O of everything you do with it. Learn to spot the accidental O(n²), match the structure to the operation you need cheap (hash for lookup, tree for order, array for access), and recognize the B-trees and Bloom filters under your tools. That fluency is what separates code that works in the demo from code that works in production.

References