Big O Notation | Ground0 Academy

What is Big O?

Big O notation describes the performance or complexity of an algorithm. It tells us how much the runtime or space requirements grow relative to the input size (n).

Why does this matter? As your data grows, inefficient algorithms can become unusably slow. Understanding Big O helps you write scalable code.

Common Complexities (Best to Worst)

Notation	Name	Description	Example
O(1)	Constant	Same time regardless of input size	Array lookup by index
O(log n)	Logarithmic	Doubles with each step (divide & conquer)	Binary search
O(n)	Linear	Grows proportionally with input	Simple loop through array
O(n log n)	Linearithmic	Good sorting algorithms	Merge sort, Quick sort
O(n²)	Quadratic	Grows with square of input	Nested loops
O(2ⁿ)	Exponential	Doubles with each addition	Recursive Fibonacci

Visual Comparison

How operations grow with input size (n):

n=10 n=100 n=1000 Growth Pattern ───────────────────────────────────────────── O(1) 1 1 1 ━━━━━━━━ Flat O(log n) 3 6 9 ╱ Slow curve O(n) 10 100 1000 ╱ Linear O(n²) 100 10000 1M ╱╱ Steep curve O(2ⁿ) 1024 HUGE! MASSIVE! ╱╱╱ Vertical cliff

Code Examples

O(1) - Constant Time

            // Accessing array by index
const arr = [1, 2, 3, 4, 5];
const first = arr[0];      // O(1)
const last = arr[arr.length - 1];  // O(1)

// Object property access
const user = { name: "Alice", age: 30 };
console.log(user.name);    // O(1)
        

O(n) - Linear Time

            // Single loop through array
function findMax(arr) {
    let max = arr[0];                    // O(1)
    for (let i = 0; i < arr.length; i++) {  // O(n)
        if (arr[i] > max) max = arr[i];
    }
    return max;                          // O(1)
}
// Total: O(1) + O(n) + O(1) = O(n)
        

O(n²) - Quadratic Time

            // Nested loops
function printPairs(arr) {
    for (let i = 0; i < arr.length; i++) {        // O(n)
        for (let j = 0; j < arr.length; j++) {    // O(n)
            console.log(arr[i], arr[j]);
        }
    }
}
// Total: O(n) × O(n) = O(n²)

// Bubble Sort (inefficient)
function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}
        

O(log n) - Logarithmic

            // Binary Search
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    
    return -1;
}
// Each iteration halves the search space: O(log n)
        

Space Complexity

Big O also applies to memory usage:

            // O(1) space - only uses a few variables
function sum(arr) {
    let total = 0;                    // O(1)
    for (let num of arr) {
        total += num;
    }
    return total;
}

// O(n) space - creates new array
function double(arr) {
    const result = [];                // O(n) space
    for (let num of arr) {
        result.push(num * 2);
    }
    return result;
}
        

Amortized Analysis

Some operations have different worst-case and average-case complexities:

            // Array.push is O(1) amortized
// Occasionally it needs to resize (O(n)), but rarely
const arr = [];
for (let i = 0; i < 1000; i++) {
    arr.push(i);  // O(1) amortized per push
}
        

Quick Reference

Operation	Array	Object/Map	Set
Access	O(1)	O(1)	N/A
Search	O(n)	O(1)	O(1)
Insert	O(n)	O(1)	O(1)
Delete	O(n)	O(1)	O(1)

← Back to Academy