What is Big O notation? Explain O(1), O(log n), O(n), O(n log n), O(n²) and O(2ⁿ) with .NET examples, and the difference between best, average, worst-case and amortised cost.

1. What Big O formally means

f(n) = O(g(n)) means: there exist constants c and n₀ such that for all n ≥ n₀, f(n) ≤ c · g(n).

In plain words, beyond some input size, f never grows faster than a constant multiple of g. The "doubling test" is a practical consequence: if cost is proportional to n², doubling n multiplies the cost by about four once n is large enough for the dominant term to win.

In interviews people say "Big O" when they usually mean the tight bound of the worst case. Saying "binary search is Θ(log n) in the worst case" is the precise version.

2. How the classes grow

Concrete numbers for n = 1,000,000 at roughly 1 ns per step:

The difference between O(n log n) and O(n²) at a million rows is milliseconds versus a timeout.

3. Where log n comes from

Any time you halve the problem each step, you get log₂ n steps:

1,000,000 -> 500,000 -> 250,000 -> ... -> 1     (about 20 halvings)

Binary search, balanced tree height and the depth of merge sort's recursion are all log n for this reason. The base of the log does not matter in Big O, because log₂ n and log₁₀ n differ only by a constant factor.

4. Amortised analysis of List<T>.Add

capacity: 4      8              16
          [####] [########]     [################]
           ^ add 5th item: allocate 8, copy 4
                  ^ add 9th: allocate 16, copy 8

Total copies after n adds ≈ 4 + 8 + 16 + ... + n < 2n. So n adds cost O(n) in total, which is amortised O(1) per add. Individual adds can still be O(n), which matters for latency-sensitive code: pre-size with new List<T>(capacity) when you know the count.

5. Average versus worst case in practice

6. Hidden complexity in .NET APIs

7. Big O is not the whole story

• Constants and cache effects: an O(n) scan of a small contiguous array often beats an O(log n) tree walk that chases pointers. For n below a few dozen, linear search in an array is frequently fastest.
• I/O dominates: one database round trip (about 1 ms) costs more than millions of in-memory operations. An O(1) algorithm that does N+1 queries loses to an O(n log n) one that does one query.
• Allocation: an O(n) LINQ pipeline that allocates per element may be slower than an O(n) loop that does not.
• Space: time and memory complexity are separate; a hash set makes duplicate detection O(n) time but costs O(n) extra memory.

8. Try it yourself

// dotnet new console; paste into Program.cs; dotnet run -c Release
using System.Diagnostics;

foreach (var n in new[] { 1_000, 10_000, 50_000 })
{
    var list = Enumerable.Range(0, n).ToList();
    var set = list.ToHashSet();

    var sw = Stopwatch.StartNew();
    int hits = 0;
    foreach (var x in list) if (list.Contains(x)) hits++; // O(n²)
    var quadratic = sw.Elapsed;

    sw.Restart();
    foreach (var x in list) if (set.Contains(x)) hits++;  // O(n)
    Console.WriteLine($"n={n,6}: List {quadratic.TotalMilliseconds,8:F1} ms, HashSet {sw.Elapsed.TotalMilliseconds,6:F2} ms");
}

Watch the List column grow about 100× when n grows 10×, while the HashSet column grows about 10×.

```csharp
// O(1): constant, independent of n
int First(int[] a) =&gt; a[0];

// O(log n): halve the search space each step
int idx = Array.BinarySearch(sortedIds, 42);

// O(n): one pass
long Sum(int[] a)
{
long s = 0;
foreach (var x in a) s += x;
return s;
}

// O(n log n): comparison sort
Array.Sort(prices);

// O(n²): nested loop over the same data
bool HasDuplicateSlow(int[] a)
{
for (int i = 0; i &lt; a.Length; i++)
for (int j = i + 1; j &lt; a.Length; j++)
if (a[i] == a[j]) return true;
return false;
}

// O(n): same answer with a HashSet (expected O(1) per Add)
bool HasDuplicateFast(int[] a)
{
var seen = new HashSet