Big O Analysis

Definition

---

Complexity Classes

---

Analysis Techniques

---

Code Pattern Recognition

// O(1) - Constant
int first = arr[0];
map.get(key);

// O(log n) - Logarithmic (halving)
while (n > 0) {
    n = n / 2;  // or n >>= 1
}

// O(n) - Linear
for (int i = 0; i < n; i++) {
    // O(1) work
}

// O(n log n) - Divide and conquer with linear merge
void mergeSort(arr, l, r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(arr, l, m);      // T(n/2)
        mergeSort(arr, m+1, r);    // T(n/2)
        merge(arr, l, m, r);       // O(n)
    }
}
// T(n) = 2T(n/2) + O(n) = O(n log n)

// O(n²) - Nested loops
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // O(1) work
    }
}

// O(2ⁿ) - Two recursive calls
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

---

Common Mistakes

---

Tips & Tricks

---