What Is Big-O Notation: Growth Rate, O, Ω, Θ and Worst Case
Big-O describes an algorithm's cost not in seconds but by how its step count grows as the input size n grows. The difference between O, Ω and Θ, choosing n correctly, best/average/worst case, and the real growth of List, HashSet and binary search from 10 to 1,000,000 elements measured with BenchmarkDotNet.
Version note: The code in this post was built and run with .NET 10 (C# 14); measurements were taken with BenchmarkDotNet 0.15.8 and tests with xUnit v3 4.0.2.
Guess First
The Bookstore catalog holds 1,000 books today. The product team is aiming for 1,000,000 next year. The code has three ways to find a book by ISBN (International Standard Book Number): Contains on a List<string>, Contains on a HashSet<string>, and Array.BinarySearch on a sorted array. Today all three answer in somewhere between a few nanoseconds and a few microseconds.
When the catalog grows a thousandfold, how much slower does each one get? A thousand times, twice, not at all? Write your answer down; halfway through the post we'll compare it with real numbers measured on one machine. One more question: since HashSet is "O(1)", is a lookup with a 100,000-character key as fast as one with a 13-character key?
Not "How Many Seconds" but "How Does It Grow"
Describing an algorithm's speed in seconds is tempting but useless. The same code takes 1.4 microseconds on the Apple M5 I'm writing this on, three times that on a five-year-old server, ten times that in a debug build. Seconds depend on the machine, the runtime, what the JIT (Just-In-Time) compiler decided that day and the state of the CPU (Central Processing Unit) cache. What we actually want to know is something else: what happens to this code when the data grows?
Big-O notation is the language that answers that question. We write the number of steps an algorithm takes as a function of the input size n: T(n). Then we look at how that function behaves for large n. "This method is O(n)" means "when n doubles, the time roughly doubles"; "O(n²)" means "when n doubles, the time quadruples." We don't give seconds, we give a growth rate.
Let's make step counting concrete. First we write two searches and count how many comparisons they make:
namespace Bookstore.Complexity;
public sealed record Book(string Isbn, string Title, string Author, decimal Price);
public static class CatalogSearch
{
// Linear search: compares the key with every book until it finds a match.
public static (Book? Book, int Comparisons) Linear(List<Book> books, string isbn)
{
var comparisons = 0;
foreach (var book in books)
{
comparisons++;
if (book.Isbn == isbn)
{
return (book, comparisons);
}
}
return (null, comparisons);
}
// Binary search over books sorted by Isbn (ordinal).
public static (Book? Book, int Comparisons) Binary(Book[] sortedBooks, string isbn)
{
int low = 0, high = sortedBooks.Length - 1, comparisons = 0;
while (low <= high)
{
var mid = low + (high - low) / 2;
comparisons++;
var cmp = string.CompareOrdinal(sortedBooks[mid].Isbn, isbn);
if (cmp == 0)
{
return (sortedBooks[mid], comparisons);
}
if (cmp < 0) low = mid + 1; else high = mid - 1;
}
return (null, comparisons);
}
}The demo app builds two catalogs of 1,000 and 1,000,000 books and searches for the first book, the last book and an ISBN that isn't in the catalog. Real output:
n = 1,000
linear best (first) : 1
linear worst (last) : 1,000
linear missing : 1,000
binary last : 10
binary missing : 10
n = 1,000,000
linear best (first) : 1
linear worst (last) : 1,000,000
linear missing : 1,000,000
binary last : 20
binary missing : 20In linear search the number of comparisons grew a thousandfold along with n. In binary search it went from 10 to 20: n grew a thousand times, the step count grew by only 10. That's because each comparison halves the search range; halve 1,000,000 twenty times and you drop below 1 (2²⁰ = 1,048,576). The first is O(n), the second O(log n).
Choosing n Correctly
The first and most often skipped step of analysis is deciding what n is. For the catalog, n is the number of books. But the same code can hide other sizes:
- For a method that walks every character of a string, n is the string length, not the record count.
- Code that matches orders to customers has two independent sizes: n orders and m customers. Writing O(n·m) is more honest than O(n²), because 1,000,000 orders with 50 customers behaves very differently from 1,000 orders with 1,000 customers.
- In a nested collection of authors and each author's books, "for each author, walk their books" is not the square of the author count. If the total number of books is K, it's O(authors + K).
The last point is a real trap. The moment you see two nested foreach loops, "O(n²)" becomes a reflex. But if the inner loop doesn't walk the same n elements on every outer iteration, only that author's own books, the total work equals the total number of books. You need to count how many times the inner body runs in total, not how many loops there are.
O, Ω and Θ: Upper Bound, Lower Bound, Tight Bound
In everyday speech we always say "Big-O", but the literature has three separate symbols. CLRS (Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein) defines them like this:
f(n) = O(g(n)) <=> exists c > 0, n0 : for all n >= n0, f(n) <= c * g(n) // upper bound
f(n) = Ω(g(n)) <=> exists c > 0, n0 : for all n >= n0, f(n) >= c * g(n) // lower bound
f(n) = Θ(g(n)) <=> f(n) = O(g(n)) and f(n) = Ω(g(n)) // tight boundO only says "grows no faster than this." So technically linear search is both O(n) and O(n²); both are correct upper bounds. But saying "O(n²)" tells nobody anything. Θ says "grows at exactly this rate." In interviews, in code review and in documentation, when someone says "this method is O(n)" they almost always mean Θ(n). In this post and the rest of the series I'll follow everyday usage and write Θ when I need to stress that a bound is tight.
The practical consequence of the definition is two simple rules: drop constant factors, drop lower-order terms. Say you counted the steps of some reporting code and got T(n) = 3n² + 20n + 5. Choose c = 4 and n0 = 21 and for every n ≥ 21 we have 3n² + 20n + 5 ≤ 4n² (at n = 21, 1,748 ≤ 1,764; at n = 20, 1,605 > 1,600, so the inequality holds from exactly 21 on). So T(n) = Θ(n²). The 20n term is 40 percent of the total at n = 10 and less than a thousandth of it at n = 10,000. For large n the dominant term wins.
Dropping constants doesn't mean "constants don't matter." Constants determine the real running time and, for small n, they often determine the winner too. Big-O only compares growth. We leave the story of constants and the cache to the last post of the series.
Best, Average and Worst Case
The second confusion comes from mixing up cases and bounds. Best, average and worst case say which input scenario we're looking at; O, Ω and Θ say how we bound the cost function in that scenario. The two are independent: "the worst case of linear search is Θ(n)" is a meaningful sentence.
The output above shows all three cases. If the book we're looking for is at the start of the list, linear search finishes in a single comparison: best case Θ(1). For the last book or an ISBN that isn't in the catalog it makes n comparisons: worst case Θ(n). If the book is at a random position it makes n/2 comparisons on average; drop the constant and the average case is Θ(n) too.
In production we mostly care about the worst case, because an SLA (Service Level Agreement) breach comes from the worst request, not the average one. Dictionary<TKey, TValue>.ContainsKey is a good example. The Microsoft docs say this method "approaches O(1)." That's an average-case statement and assumes a well-distributed GetHashCode. If every key produces the same hash, every lookup walks the same bucket's chain end to end and the worst case drops to Θ(n). We'll measure that with a bad GetHashCode in the last post of the series. For the full API (Application Programming Interface) complexity table, see "Immutable Collections in C# and Choosing the Right Collection" in the C# Collections series; I won't repeat it here.
Common Growth Classes
The vast majority of real code falls into one of a few classes. To build intuition I wrote a small program that computes how many steps each class means for different n:
n log2 n n log2 n n^2 2^n n!
10 3.3 33.2 100 1.02E+03 3.63E+06
20 4.3 86.4 400 1.05E+06 2.43E+18
100 6.6 664 1E+04 1.27E+30 9.33E+157
1,000 10.0 9.97E+03 1E+06 1.07E+301 Infinity
1,000,000 19.9 1.99E+07 1E+12 Infinity InfinityThe Infinity values are not a bug: 1,000! and 2¹⁰⁰⁰⁰⁰⁰ exceed the largest value a double can hold (about 1.8 × 10³⁰⁸). The chart below draws the same classes with both axes logarithmic:
With a Bookstore example for each:
| Class | Bookstore example | When n doubles |
|---|---|---|
O(1) | Reading a cart item by index, a HashSet lookup (average) | unchanged |
O(log n) | Binary search in a sorted price list | one more step |
O(n) | Summing all orders | twice |
O(n log n) | Sorting the catalog by title | slightly more than twice |
O(n²) | Comparing every book with every book to find duplicates | four times |
O(2ⁿ) | Trying every subset of an n-book campaign | squared |
O(n!) | Trying every route of a courier visiting n stores | even adding 1 to n multiplies it by n+1 |
The note under the chart is a rough but useful yardstick: assume a core doing about 10⁹ simple operations per second and an O(n²) algorithm takes about 17 minutes at n = 10⁶, while an O(n log n) one takes 20 milliseconds. O(2ⁿ) takes about 13 days at n = 50 and 36 years at n = 60.
Measuring: List, HashSet and Binary Search
Back to the question from the guessing section. I measured the three lookups with BenchmarkDotNet on 10, 1,000 and 1,000,000 elements. The key we look for is the last element of the list, the worst case for linear search:
[MemoryDiagnoser]
public class CatalogLookupBenchmarks
{
private List<string> _list = [];
private HashSet<string> _set = [];
private string[] _sorted = [];
private string _target = "";
[Params(10, 1_000, 1_000_000)]
public int N;
[GlobalSetup]
public void Setup()
{
_list = [.. Enumerable.Range(1, N).Select(CatalogFactory.IsbnOf)];
_set = [.. _list];
_sorted = [.. _list.Order(StringComparer.Ordinal)];
_target = CatalogFactory.IsbnOf(N); // worst case for the list: last element
}
[Benchmark(Baseline = true)]
public bool ListContains() => _list.Contains(_target);
[Benchmark]
public bool HashSetContains() => _set.Contains(_target);
[Benchmark]
public bool SortedArrayBinarySearch() => Array.BinarySearch(_sorted, _target, StringComparer.Ordinal) >= 0;
}Result (Apple M5, macOS 27.0.1, .NET 10.0.13, Arm64 RyuJIT; table trimmed):
| Method | N | Mean | Ratio |
|------------------------ |-------- |-----------------:|------:|
| ListContains | 10 | 14.142 ns | 1.00 |
| HashSetContains | 10 | 4.241 ns | 0.30 |
| SortedArrayBinarySearch | 10 | 9.926 ns | 0.70 |
| ListContains | 1000 | 1,446.844 ns | 1.000 |
| HashSetContains | 1000 | 5.035 ns | 0.003 |
| SortedArrayBinarySearch | 1000 | 26.687 ns | 0.018 |
| ListContains | 1000000 | 1,390,590.370 ns | 1.002 |
| HashSetContains | 1000000 | 4.476 ns | 0.000 |
| SortedArrayBinarySearch | 1000000 | 39.618 ns | 0.000 |Theory and measurement are very close. Going from 1,000 to 1,000,000, List.Contains got 961 times slower (just under a thousand; there's measurement noise on the big array too), binary search got 1.48 times slower (log₂ 10⁶ / log₂ 10³ = 2; the gap comes from fixed costs), and HashSet didn't change at all within measurement precision. None of them allocated. How this benchmark is set up and what the columns of the result table mean was covered in "Performance in C#: Allocations, Structs and Measuring with BenchmarkDotNet" in the Advanced C# series.
In Production
Big-O is a forecasting tool; its real value is that it makes you ask "what happens to this code when the data grows" before there's a problem. A few habits keep that question concrete in production.
Make n visible in the logs. "Matched orders, 340 ms" says little. "orders=48,000, customers=1,200, 340 ms" tells you, when two weeks later the same line reads "orders=96,000, 1,350 ms", that growth is quadratic, not linear.
O(1) has an input too. I measured the second question from the start of the post. A HashSet<string> holds three keys; I made the length of the key being looked up 13, 1,000 and 100,000 characters. The size of the hash table doesn't change, so the lookup is O(1) in the number of elements. But computing the string's hash and checking equality reads every character:
| Method | KeyLength | Mean |
|---------------- |---------- |--------------:|
| HashSetContains | 13 | 6.044 ns |
| HashSetContains | 1000 | 219.886 ns |
| HashSetContains | 100000 | 21,088.598 ns |When the key got 100 times longer, the lookup got about 96 times slower. So a HashSet lookup is O(1) in the number of elements and O(k) in the key length k. Writing down both sizes is another example of choosing n correctly.
Finally, the growth class doesn't make the decision at small n. Even in the 10-element measurement HashSet won, but by a few nanoseconds; at that scale readability and memory may be the better criteria. Big-O speaks loudest where n is small today but large tomorrow: lists that grow per system rather than per user, logs appended every day, growing catalogs.
Common Pitfalls
"O(1) is always fast." O(1) only means "independent of n." A fixed 50-millisecond network call is O(1) too. And as you saw above, a hidden cost such as hashing can depend on a different size.
"O(n²) is always slow." At n = 10, 100 steps are nothing. Even .NET's own Array.Sort uses insertion sort, which is O(n²), for partitions of 16 elements or fewer, because its constant is lower at small n.
The wrong n. Count the total number of times the body runs, not the number of loops. Two nested loops can do work proportional to the total element count; a single line of LINQ (Language Integrated Query) can hide a loop. That's exactly the topic of the next post.
Treating the average case as a guarantee. Dictionary is O(1) on average. Attacker-controlled keys or a bad GetHashCode can bring the worst case into production.
Using Big-O instead of measuring. Of two O(n) algorithms, one can take ten times as long as the other. Analysis tells you which algorithm scales; measurement tells you which one is faster today.
A Small Experiment
★☆☆ Run CatalogSearch.Linear on a 10,000-book catalog for 1,000 randomly chosen ISBNs and print the average number of comparisons. How close is it to n/2?
★★☆ For T(n) = 5n log₂ n + 300n, compute the n at which the 5n log₂ n term overtakes 300n. Which term dominates below that point, and how does that mislead someone measuring the algorithm on a small catalog?
★★★ Build a Dictionary<string, List<Book>> of authors and their books; keep the author count fixed, double the total number of books and measure the time of "walk every book of every author" with BenchmarkDotNet. Then keep the book count fixed and increase the author count. Which size determines the time?
In this post we learned the language of cost, but we always counted steps by hand. In the next post we'll learn to read them straight from the code: sequential and nested loops, loops that halve every step, writing recurrences for recursion, and the hidden loops LINQ hides in a single line.