Big-O notation — time and space complexity — Data Structures & Algorithms

1. Big-O notation — time and space complexity

Basic★ Must knowLesson 1 of 10

Big-O describes how the running time (or memory) grows as the input size n grows, ignoring constants.

Big-O	Name	Example	n = 1,000,000 → roughly
O(1)	Constant	Array index, dictionary lookup	1 step
O(log n)	Logarithmic	Binary search, B-tree index seek	20 steps
O(n)	Linear	Loop over a list, table scan	1,000,000
O(n log n)	Linearithmic	Good sorting (merge, heap, quick average)	20,000,000
O(n²)	Quadratic	Nested loops over the same data, bubble sort	10¹² — too slow
O(2ⁿ)	Exponential	All subsets, naive Fibonacci	impossible
O(n!)	Factorial	All permutations	impossible

csharp

bool ContainsDuplicate_N2(int[] a)            // O(n²) time, O(1) space
{
    for (int i = 0; i < a.Length; i++)
        for (int j = i + 1; j < a.Length; j++)
            if (a[i] == a[j]) return true;
    return false;
}

bool ContainsDuplicate_N(int[] a)             // O(n) time, O(n) space — trade memory for speed
{
    var seen = new HashSet<int>();
    foreach (var x in a) if (!seen.Add(x)) return true;
    return false;
}

Rules: drop constants (O(2n) → O(n)); keep the dominant term (O(n² + n) → O(n²)); different inputs get different letters (O(a + b), O(a × b)); amortised O(1) means usually O(1), occasionally more (e.g. List<T>.Add when it must grow).

Best / average / worst case: quicksort is O(n log n) on average but O(n²) in the worst case; hash lookups are O(1) average, O(n) worst (all keys collide).