Code Patterns

Learn to recognize complexity by looking at code structure. Each pattern has telltale signs that reveal its Big O.

Interactive Step Counter

Select a code example and watch the operations count as it runs. Compare the actual count to the Big O prediction.

O(n)Sum Array

Input Size (n): 5

Java Code

1int sum(int[] arr) {

2 int total = 0;

3 for (int i = 0; i < arr.length; i++) {

4 total += arr[i];

5 }

6 return total;

Speed:

Actual Operations

Predicted O(n)

Why O(n)? We visit each element exactly once, so operations grow linearly with array size.

O(1)Constant Patterns

Array Index Access

int getFirst(int[] arr) {
    return arr[0];
}

Why O(1)? Direct memory address calculation - always one operation.

Arithmetic Operations

int calculate(int a, int b) {
    int sum = a + b;
    int product = a * b;
    int result = sum + product;
    return result;
}

Why O(1)? Fixed number of operations regardless of input values.

O(log n)Logarithmic Patterns

Binary Search Pattern

int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Why O(log n)? Search space halves each iteration. 1000 → 500 → 250 → 125... only ~10 steps!

Doubling Loop

void doublingLoop(int n) {
    int i = 1;
    while (i < n) {
        System.out.println(i);
        i = i * 2;  // Doubles each time
    }
}

Why O(log n)? i grows as 1, 2, 4, 8, 16... reaches n in log₂(n) steps.

O(n)Linear Patterns

Single Loop

void printAll(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
}

Why O(n)? Loop runs exactly n times where n is array length.

Linear Search

int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

Why O(n)? Worst case: target is last or not present, checking all n elements.

Sequential Loops (Still O(n)!)

void process(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // First pass
    }
    for (int i = 0; i < arr.length; i++) {
        // Second pass
    }
}

Why O(n)? O(n) + O(n) = O(2n) = O(n). Constants are dropped!

Common Mistake:Students often think this is O(n²) because there are two loops.

NOT O(n²): Constant Inner Loop

void notQuadratic(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < 5; j++) {  // Fixed iterations!
            System.out.println(arr[i]);
        }
    }
}

Why O(n)? Inner loop is constant (5 iterations), not dependent on n. Total: 5n = O(n).

Common Mistake:Nested loops are NOT always O(n²). Check if inner loop depends on n!

O(n log n)Linearithmic Patterns

Linear × Logarithmic

void mergePattern(int[] arr) {
    // Outer: log(n) levels (like merge sort)
    for (int size = 1; size < arr.length; size *= 2) {
        // Inner: n elements processed at each level
        for (int i = 0; i < arr.length; i++) {
            process(arr, i, size);
        }
    }
}

Why O(n log n)? Outer loop doubles (log n iterations), inner processes all n elements.

O(n²)Quadratic Patterns

Nested Loops

void nestedLoops(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + arr[j]);
        }
    }
}

Why O(n²)? Inner loop runs n times for EACH of the n outer iterations: n × n = n².

Triangular Nested Loop

void upperTriangle(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i; j < arr.length; j++) {
            System.out.println(arr[i] + arr[j]);
        }
    }
}

Why O(n²)? Inner loop runs n, n-1, n-2... times. Sum = n(n+1)/2 ≈ n²/2 = O(n²).

O(2^n)Exponential Patterns

Recursive Branching

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

Why O(2^n)? Each call makes 2 recursive calls. Tree of calls doubles at each level.

Quick Pattern Recognition Guide

Look for Loops

• No loops: Probably O(1)
• Single loop (0 to n): O(n)
• Nested loops (both 0 to n): O(n²)
• Loop that halves (n/2): O(log n)

Check Loop Bounds

• Inner loop constant (0 to 5): Still O(n)!
• Inner loop depends on outer (j = i): Still O(n²)
• Loop increments by *2: O(log n)

Recursion Hints

• Single recursive call: Usually O(n) or O(log n)
• Two recursive calls: Often O(2^n)
• Divide & conquer: Usually O(n log n)

Sequential Operations

• O(n) + O(n) = O(n), not O(n²)
• O(n) + O(n²) = O(n²)
• Drop constants: O(3n) = O(n)