Big O Complexity: How Fast Does It Grow?

Big O answers one question:

How does the work grow when the input grows?

Input size (n)     Work
──────────────     ────
10 items           ?
1,000 items        ?
1,000,000 items    ?

It ignores constants and focuses on the shape of growth.

The Common Ones

O(1)        Constant
O(log n)    Logarithmic
O(n)        Linear
O(n log n)  Linearithmic
O(n²)       Quadratic
O(2ⁿ)       Exponential

Visual growth:

n = 1     10      100     1,000    1,000,000
────────────────────────────────────────────
O(1)      1       1       1        1
O(log n)  0       ~3      ~7       ~20
O(n)      1       10      100      1,000,000
O(n log n)1       ~33     ~664     ~20M
O(n²)     1       100     10,000   1,000,000,000,000
O(2ⁿ)     2       1,024   huge     impossible

What Each Feels Like

Complexity	Everyday meaning	Example
O(1)	Instant, no matter the size	Array index, Hash lookup
O(log n)	Grows very slowly	Binary search, balanced tree
O(n)	Grows with the data	Loop over a list once
O(n log n)	Sorting territory	Merge sort, good sorts
O(n²)	Nested loops	Compare every pair
O(2ⁿ)	Explodes	Naive recursion, subsets

Visual Decision

Need to look something up?
        │
   ┌────┴────┐
  Hash?     Sorted?
   │         │
   ▼         ▼
 O(1)     O(log n)

Need to process every item once?
        │
        ▼
      O(n)

Need to sort?
        │
        ▼
   O(n log n)

Nested loops over the same data?
        │
        ▼
      O(n²)   ← danger zone

Real .NET Examples

// O(1)
var item = list[5];
dict.TryGetValue(key, out var value);

// O(log n)
Array.BinarySearch(sorted, target);

// O(n)
foreach (var x in list) { ... }
list.Contains(item);          // List
list.Where(x => x > 10);      // LINQ (usually)

// O(n log n)
list.OrderBy(x => x.Name);    // LINQ OrderBy
Array.Sort(array);

// O(n²)
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        // compare every pair

What Big O Ignores

O(2n)     →  still O(n)
O(n + 100)→  still O(n)
O(5)      →  O(1)

Constants matter in practice, but Big O cares about growth rate.

When It Actually Matters

Situation	Care about Big O?
n < 100	Rarely
n = 10,000	Sometimes
n = 1,000,000+	Yes
Hot path / API under load	Yes
One-time admin job	Less critical
Nested loops on user data	Always check

Rule of thumb:
If the input can grow without a hard limit,
think about the complexity.

Common Traps

❌ list.Contains() inside a loop over the same list
   → O(n²)

❌ Nested foreach on large collections
   → O(n²)

❌ Calling .ToList() or .OrderBy() repeatedly
   → hidden extra cost

✅ Use HashSet for lookups
   → O(1)

✅ Sort once, then binary search
   → O(n log n) + O(log n)

Final Takeaway

O(1) / O(log n)  →  scale almost for free
O(n)             →  scales with data (usually fine)
O(n log n)       →  sorting cost (acceptable)
O(n²)            →  will hurt as data grows
O(2ⁿ)            →  only for tiny n

Big O is not about micro-optimizing every line.
It’s about avoiding algorithms that explode when the data gets real.