Big O & Complexity

Big O notation describes how the runtime or memory usage of an algorithm grows as the input size grows. It focuses on the worst-case scenario and ignores constants and smaller terms.

Key ideas:

• Time complexity - how many operations an algorithm performs
• Space complexity - how much extra memory an algorithm uses

Big O answers: "If I double the input, does my algorithm get 2x slower? 4x slower? Or does it not matter?"

// O(1) - Constant time: always 1 operation
int GetFirst(int[] arr) => arr[0];

// O(n) - Linear time: n operations
int Sum(int[] arr) {
    int total = 0;
    foreach (var x in arr) total += x;
    return total;
}

// O(n²) - Quadratic time: n² operations
void PrintPairs(int[] arr) {
    for (int i = 0; i < arr.Length; i++)
        for (int j = 0; j < arr.Length; j++)
            Console.WriteLine($"{arr[i]},{arr[j]}");
}

1. Drop constants An algorithm that does 2n + 3 operations is still O(n). We only care about the growth rate.

2. Drop non-dominant terms If an algorithm is O(n + n²), it simplifies to O(n²). The n² term dominates.

3. Different inputs = different variables If you have two arrays of different sizes, use different variables: O(a * b) not O(n²).

4. Worst case Always analyze the worst-case scenario unless specified otherwise.

// O(n) - drop the constant 2
void PrintTwice(int[] arr) {
    foreach (var x in arr) Console.WriteLine(x);  // n
    foreach (var x in arr) Console.WriteLine(x);  // n
} // 2n → O(n)

// O(n²) - drop non-dominant n term
void Process(int[] arr) {
    foreach (var x in arr) Console.WriteLine(x);   // O(n)
    foreach (var x in arr)                          // O(n²)
        foreach (var y in arr)
            Console.WriteLine($"{x},{y}");
} // O(n + n²) → O(n²)

// O(a + b) - different inputs
void Merge(int[] a, int[] b) {
    foreach (var x in a) Console.WriteLine(x);
    foreach (var y in b) Console.WriteLine(y);
} // O(a + b), NOT O(n)

Space complexity measures the extra memory an algorithm uses beyond the input itself.

Stack space matters too: Recursive calls consume space on the call stack. A recursive function that calls itself n times before returning uses O(n) stack space.

// O(1) space - in-place
void ReverseInPlace(int[] arr) {
    int i = 0, j = arr.Length - 1;
    while (i < j) {
        (arr[i], arr[j]) = (arr[j], arr[i]);
        i++; j--;
    }
}

// O(n) space - extra array
int[] CopyArray(int[] arr) {
    var copy = new int[arr.Length];
    Array.Copy(arr, copy, arr.Length);
    return copy;
}

// O(n) stack space - recursion depth
int Factorial(int n) {
    if (n <= 1) return 1;
    return n * Factorial(n - 1);
} // Call stack grows to n frames

Complexity analysis tells you whether your code will actually finish.

When to worry about Big O:

• Large inputs (n > 10,000) - O(n²) can become unusable
• Real-time systems - response time matters
• Interview problems - you will be asked to analyze and optimize
• APIs / production code - users won't tolerate slowdowns

When NOT to worry:

• Small, fixed-size inputs (n < 100) - any algorithm is fine
• Prototypes / one-off scripts - clarity > performance
• Premature optimization - don't optimize before you measure

A practical guide:

"O(2n) is the same as O(2ⁿ)" No - O(2n) drops the constant and becomes O(n). O(2ⁿ) is exponential and completely different.

"This is O(n) so it's fast" O(n) with n = 10^12 is 10 trillion operations. Always check the actual input size.

"The best case is O(1), so the algorithm is fast" Always analyze worst case. Best case is rarely relevant.

"I don't need to worry about stack space" Recursive functions consume O(depth) stack space. Deep recursion (10,000+ calls) causes stack overflow.

"Drop constants means constants don't matter" Constants still matter in practice. O(100n) is 100x slower than O(n), even though both are "O(n)".

"What is the complexity of this function?" Walk through: count nested loops, recursive calls, and extra data structures.

"Can you optimize this?" Common pattern: O(n²) → O(n) using a hash map, or O(n) → O(log n) using binary search.

"What if the input was 10x larger?" Use your answer to predict feasibility. An O(n²) algorithm on 1M elements = impossible. An O(n log n) algorithm on 1M elements = ~20M operations, fine.