Big O Notation

Big O describes how an algorithm's performance scales as the input size grows. It measures the worst-case growth rate, ignoring constants and lower-order terms.

Common Complexities

C# Examples

// O(1) — Constant
int first = arr[0];

// O(log n) — Logarithmic
int idx = Array.BinarySearch(sorted, target);

// O(n) — Linear
foreach (var item in list)
    Console.WriteLine(item);

// O(n log n) — Linearithmic
Array.Sort(data);

// O(n^2) — Quadratic
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        Console.Write("*");

// O(2^n) — Exponential
int Fib(int n) => n <= 1 ? n : Fib(n-1) + Fib(n-2);

Practical Tips

1. Drop constants: O(2n) is just O(n)
2. Drop lower terms: O(n^2 + n) is just O(n^2)
3. Nested loops multiply: Two nested loops over n = O(n^2)
4. Sequential code adds: O(n) + O(m) = O(n + m)
5. Halving = logarithmic: If you cut the problem in half each step, it's O(log n)

Space Complexity

Big O also applies to memory usage:

// O(1) space — modifies array in place
Array.Sort(data);

// O(n) space — creates a new array
var copy = data.ToArray();

// O(n) space — recursion uses stack frames
void Recurse(int n) {
    if (n == 0) return;
    Recurse(n - 1);
}