Big O Notation - Simple Guide

What is Big O?

Big O describes how much slower your code gets as you throw more data at it.

Think of it as a speedometer for your algorithms. It tells you: "If I give you 10 times more data, will you take 10 times longer? 100 times longer? Or stay the same?"

Big O ignores the little details and focuses on the main thing that makes your code slower as data grows.

O(1)

Constant Time

Lightning Fast ⚡

Restaurant Analogy: Flipping the "OPEN" sign. Doesn't matter if you have 10 or 1000 customers, it takes the same time.

// Getting first item from array
$numbers = [5, 10, 15, 20];
echo $numbers[0];

// Always instant, no matter array size!
                

When: Direct access to data, like array indexing or hash table lookup.

O(log n)

Logarithmic Time

Very Fast 🔍

Phone Book Search: Open to middle, check if name comes before or after, repeat with half. Even with a million names, only ~20 tries!

// Binary search in sorted array
$numbers = [1, 3, 5, 7, 9, 11, 13];
$target = 9;
$left = 0;
$right = count($numbers) - 1;

while ($left <= $right) {
    $mid = floor(($left + $right) / 2);
    if ($numbers[$mid] === $target) {
        break; // Found it!
    }
    // Cut problem in half each time
}
                

When: Dividing the problem in half repeatedly, like binary search.

O(n)

Linear Time

Acceptable 📈

ID Check Line: Check every customer's ID. 10 customers = 10 checks. 100 customers = 100 checks. Double the work for double the people.

// Finding a specific number
$numbers = [5, 10, 15, 20, 25];
$target = 20;

foreach ($numbers as $num) {
    if ($num === $target) {
        echo "Found it!";
        break;
    }
}
// Might check every single item
                

When: Looking through every item once, like a simple search or loop.

O(n²)

Quadratic Time

Slow Down! 🐌

Handshake Party: Everyone shakes hands with everyone else. 10 people = ~100 handshakes. 100 people = ~10,000 handshakes. Yikes!

// Nested loops - comparing all pairs
$numbers = [1, 2, 3, 4, 5];

for ($i = 0; $i < count($numbers); $i++) {
    for ($j = 0; $j < count($numbers); $j++) {
        // Compare each with each
        if ($i !== $j) {
            // Do something
        }
    }
}
// 5 items = 25 operations
// 100 items = 10,000 operations!
                

When: Loop inside a loop. Avoid with large datasets!

Complexity	Operations for 1,000 items	Speed Rating	Example
O(1)	1 operation	Excellent	Array lookup
O(log n)	~10 operations	Excellent	Binary search
O(n)	1,000 operations	Good	Simple loop
O(n log n)	~10,000 operations	OK	Efficient sorting
O(n²)	1,000,000 operations	Slow	Nested loops

🚀 Big O Notation

What is Big O?

Constant Time

Logarithmic Time

Linear Time

Quadratic Time

Performance Comparison

🎯 The Simple Rule