Big O & Complexity

Imagine you have a phone book with 1,000,000 names, and you're looking for "Zebra, Alice."

Strategy A - Scan from page 1: You start at page 1 and flip through every single page until you find "Zebra, Alice." If the name is at the very end, you check all 1,000,000 entries. Worst case? 1,000,000 checks.

Strategy B - Open to the middle and compare: You open to the middle. If "Zebra" comes after the current page, you throw away the first half and search the second half. You repeat - cutting the remaining pages in half each time. Worst case? About 20 checks. (Try it: 1,000,000 → 500,000 → 250,000 → ... how many steps to get to 1?)

That's the difference between O(n) (Strategy A) and O(log n) (Strategy B). And the whole point of this module is to give you a simple language to talk about these differences.

When you write code, you're always making choices. Big O helps you answer: "If my input gets 10x bigger, does my code get 10x slower, 100x slower, or barely slower at all?"

// Strategy A: Linear scan - O(n) - check every entry
bool FindLinear(List<string> phoneBook, string target) {
    foreach (var name in phoneBook)
        if (name == target) return true;
    return false;
}

// Strategy B: Binary search - O(log n) - cut in half each time
// (Requires sorted list. We'll cover this in the Sorting & Searching module.)
bool FindBinary(List<string> phoneBook, string target) {
    int left = 0, right = phoneBook.Count - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int cmp = string.Compare(phoneBook[mid], target);
        if (cmp == 0) return true;
        if (cmp < 0) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

Big O notation is the language we use to talk about how fast (or slow) an algorithm is. Think of it as a speed rating for code.

Two key ideas:

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

Big O ignores the small stuff. It doesn't care if your computer is fast or slow, or if one loop took 5ms vs 10ms. It cares about how the runtime grows as the input gets bigger.

So instead of saying "this takes 4.2 microseconds on my laptop," Big O says "this grows linearly with input size - O(n)."

The "O" stands for "order of" (as in "on the order of"). And inside the parentheses, you put how the cost grows relative to the input size.

// O(1) - Constant time: same number of operations no matter the input size
int GetFirst(int[] arr) => arr[0];

// O(n) - Linear time: if array is 10x bigger, this is 10x slower
int Sum(int[] arr) {
    int total = 0;
    foreach (var x in arr) total += x;
    return total;
}

// O(n²) - Quadratic time: if array is 10x bigger, this is 100x slower
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]}");
}

Here are the complexity classes you'll see most often. They're listed from fastest to slowest:

O(1) - Constant time No matter how big the input, it takes the same time. Example: looking up an array element by index. arr[0] on a 10-element array is the same speed as on a 10-million-element array.

O(log n) - Logarithmic time Each step cuts the problem in half. Doubling the input adds just one extra step. Example: the phone book strategy (binary search) - 1 million entries takes ~20 steps, 2 million takes ~21 steps.

O(n) - Linear time Time grows proportionally with input size. 10x more input = 10x more work. Example: summing all numbers in an array, or scanning a list to find an item.

O(n log n) - Linearithmic time A bit worse than linear, but still practical for large inputs. Example: sorting algorithms like Merge Sort and Heap Sort.

O(n²) - Quadratic time Nested loops. 10x more input = 100x more work. Example: comparing every element to every other element (nested for loops).

O(2ⁿ) - Exponential time Forget about large inputs. Even n = 50 is too many operations. Example: the naive recursive Fibonacci (we'll look at this in the Recursion module).

Here's how they stack up:

Big O has a few simple rules that make analysis easier. Once you internalize these, you can estimate complexity at a glance.

Rule 1: Drop constants. An algorithm that does 2n + 3 operations is still O(n). Constants don't change the growth pattern - n, 2n, and 100n all grow linearly.

Rule 2: Drop non-dominant terms. If your algorithm is O(n + n²), it simplifies to O(n²). The n² term dominates as n grows large, so the n term becomes irrelevant.

Rule 3: Different inputs get different variables. If you have two arrays of different sizes, don't call them both n. Use a and b. O(a * b) is very different from O(n²).

Rule 4: Always analyze the worst case. Unless someone specifically asks for the best or average case, assume worst case. That's what Big O measures.

// 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, different variables
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)

Time isn't the only resource. Space complexity measures how much extra memory your algorithm needs beyond the input itself.

Same Big O rules apply, just for memory instead of time.

• O(1) space - you're rearranging things in-place, no extra storage
• O(n) space - you're creating a copy of the data, or using a data structure that grows with input
• O(n²) space - you're building a 2D grid of size n×n

One sneaky source of space usage: the call stack. Every time a function calls itself (recursion), it pushes a frame onto the stack. A recursive function that calls itself n times before returning uses O(n) stack space. We'll explore this more in the Recursion module.

// O(1) space - in-place, no extra memory
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 - creates an 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

Big O analysis tells you whether your code will finish in a reasonable time - or whether it'll grind to a halt.

Care about Big O when:

• Your input could be large (n > 10,000) - O(n²) can become unusable
• You're building an API or product - users notice slowdowns
• You're in an interview - you'll be asked to analyze and optimize

Don't obsess when:

• The input is small and fixed (n < 100) - any algorithm is fine
• You're writing a one-off script - clarity > performance
• You haven't measured yet - don't optimize before you know what's slow

Quick reference:

"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. Never confuse linear with exponential.

"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 the worst case. Best case is rarely relevant - it's the worst case that breaks production.

"I don't need to worry about stack space" Recursive functions consume O(depth) stack space. Deep recursion (10,000+ calls) causes stack overflow. We'll revisit this in the Recursion module.

"Drop constants means constants don't matter" In Big O analysis, yes. In practice, no. O(100n) is 100x slower than O(n), even though both simplify to O(n).

"What is the complexity of this function?" Walk through: count nested loops, recursive calls, and extra data structures. One loop over n items → O(n). Two nested loops → O(n²). A loop that halves the input each time → O(log n).

"Can you optimize this?" Common patterns: O(n²) → O(n) using a hash map (next module!), or O(n) → O(log n) using binary search (covered later in Sorting & Searching).

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

Now that you have a language to talk about algorithm speed, you're ready to look at actual data structures - starting with the most fundamental one: Arrays & Strings.

Arrays are the building block of almost everything else in this course. As you learn them, pay attention to the complexity of each operation (access, search, insert, delete). You'll see the patterns we discussed here in action.

The next few modules will follow a similar structure: here's a data structure, here's what it's good at, here's what it's bad at, and here's when you'd use it instead of something else. By the end, you'll have a mental toolbox - where each tool's strengths and weaknesses are clear.

Next up: Arrays & Strings