⏱️ Time & Space Complexity Analysis

🟢 Beginner Foundation 45 min read

🤔 What is Complexity Analysis?

Complexity Analysis measures how the time and space requirements of an algorithm grow as the input size grows. It helps us compare algorithms without running them on actual hardware.

Imagine two sorting algorithms. One takes 1 second for 1000 items, the other takes 10 seconds. But what happens with 1 million items? Complexity analysis answers this before you write production code.

📐 Big O Notation - The Universal Language

Big O describes the upper bound (worst-case) growth rate. It answers: "As input size approaches infinity, how does the algorithm scale?"

Notation	Name	Example	1K items	1M items	Rating
O(1)	Constant	Array access by index	1	1	⭐⭐⭐⭐⭐
O(log n)	Logarithmic	Binary Search	~10	~20	⭐⭐⭐⭐⭐
O(n)	Linear	Linear Search, Single loop	1K	1M	⭐⭐⭐⭐
O(n log n)	Linearithmic	Merge Sort, Quick Sort	~10K	~20M	⭐⭐⭐
O(n²)	Quadratic	Bubble Sort, Nested loops	1M	1T	⭐⭐
O(2ⁿ)	Exponential	Recursive Fibonacci	2¹⁰⁰⁰	💀	⭐
O(n!)	Factorial	TSP brute force	1000!	💀💀	☠️

📈 Growth Rate Visualization


Input Size (n) →→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→
O(1):     █  (flat line - perfect!)
O(log n): ██▌ (grows very slowly)  
O(n):     ████████████████████████ (steady growth)
O(n²):    ████████████████████████████████████████████ (🚀)
O(2ⁿ):    ████████████████████████████████████████████████████████ (💥)

🧮 How to Calculate Time Complexity

Rule 1: Drop Constants

// O(2n) → O(n) — we drop the constant 2
for ($i = 0; $i < count($arr); $i++) { echo $arr[$i]; }
for ($i = 0; $i < count($arr); $i++) { echo $arr[$i]; }

Rule 2: Drop Non-Dominant Terms

// O(n² + n) → O(n²) — n² dominates as n grows
for ($i = 0; $i < $n; $i++) {          // O(n)
    for ($j = 0; $j < $n; $j++) {      // O(n²)
        echo $i + $j;
    }
}

Rule 3: Different Inputs → Different Variables

// O(a + b), NOT O(2n)
function process(array $a, array $b) {
    foreach ($a as $x) { /* ... */ }  // O(len(a))
    foreach ($b as $y) { /* ... */ }  // O(len(b))
}

Rule 4: Add for Sequential, Multiply for Nested

// Sequential: O(n) + O(m) = O(n + m)
// Nested: O(n) * O(m) = O(n * m)

for ($i = 0; $i < $n; $i++)          // O(n)
    for ($j = 0; $j < $m; $j++)      // O(m)
        echo $i + $j;                // Total: O(n * m)

🔍 Analyzing Common Patterns

Pattern 1: Simple Loop → O(n)

for ($i = 0; $i < $n; $i++) {
    // constant work here
}

Pattern 2: Loop with Halving → O(log n)

$i = $n;
while ($i > 1) {
    $i = intdiv($i, 2);  // i: n → n/2 → n/4 → ... → 1
    // log₂(n) iterations
}

Pattern 3: Nested Loops → O(n²)

for ($i = 0; $i < $n; $i++)
    for ($j = 0; $j < $n; $j++)
        echo $i, $j;  // n * n = n² operations

Pattern 4: Two Pointers → O(n)

$left = 0; $right = count($arr) - 1;
while ($left < $right) {
    // Each iteration moves left forward OR right backward
    $left++;  // or $right--;
}
// Total iterations ≤ n, so O(n)

💾 Space Complexity

Space complexity measures the extra memory an algorithm needs (excluding input storage).

O(1) Space → In-Place

function sum(array $arr): int {
    $total = 0;  // only 1 variable
    foreach ($arr as $x) $total += $x;
    return $total;
} // O(1) space - only uses $total

O(n) Space → New Array

function double(array $arr): array {
    $result = [];  // new array of size n
    foreach ($arr as $x) $result[] = $x * 2;
    return $result;
} // O(n) space - creates new array

📊 Best, Worst & Average Case

Case	Meaning	Example: Linear Search
Best Case Ω	Minimum time possible	Ω(1) — target is first element
Average Case Θ	Expected time for random input	Θ(n) — check half the array
Worst Case O	Maximum time possible	O(n) — target is last or not present

Interview Tip: Unless specified otherwise, always discuss worst-case complexity. But if an algorithm has good average-case (like QuickSort), mention it!

🐘 PHP Built-in Function Complexities

Function	Time	Notes
`isset($arr[$key])`	O(1)	Hash table lookup
`in_array($val, $arr)`	O(n)	Linear search
`array_search($val, $arr)`	O(n)	Linear search
`array_key_exists($key, $arr)`	O(1)	Hash lookup
`sort($arr)`	O(n log n)	Quicksort (PHP 8)
`array_push($arr, $val)`	O(1)	Amortized
`array_unshift($arr, $val)`	O(n)	Must reindex
`count($arr)`	O(1)	Stored internally

🧪 Live Complexity Comparison

Let's compare O(n) vs O(n²) with actual PHP code:

<?php
// O(n) - Linear
function sumArray(array $arr): int {
    $sum = 0;
    foreach ($arr as $x) $sum += $x;  // n iterations
    return $sum;
}

// O(n²) - Quadratic (print all pairs)
function printAllPairs(array $arr): void {
    $n = count($arr);
    for ($i = 0; $i < $n; $i++)         // n times
        for ($j = 0; $j < $n; $j++)     // n times each
            echo "[{$arr[$i]},{$arr[$j]}] "; // n² total
}

// Test with different sizes
$sizes = [10, 100, 1000, 10000];
foreach ($sizes as $n) {
    $arr = range(1, $n);

    $start = microtime(true);
    sumArray($arr);
    $linearTime = microtime(true) - $start;

    echo "n=$n: O(n)=" . round($linearTime*1000, 4) . "ms\n";
    // Try O(n²) for smaller n only!
}

💼 Interview Questions

O(1) - Constant time. Arrays store elements in contiguous memory, so the address of any element can be calculated directly: base_address + (index × element_size).

O(log n). The loop variable doubles each time: 1, 2, 4, 8, 16, ..., n. This means it takes log₂(n) steps to reach n. This pattern appears in Binary Search and divide-and-conquer algorithms.

Amortized analysis averages the cost over a sequence of operations. Example: PHP's dynamic array ($arr[] = $val) is usually O(1), but occasionally O(n) when it needs to resize. However, because resizes happen geometrically less often (double capacity each time), the amortized cost per push is still O(1).

⚠️ Common Mistakes

❌ Mistake: Saying O(2n) instead of O(n).
✅ Fix: Drop constants. Big O describes growth rate, not exact operations.

❌ Mistake: Ignoring space complexity.
✅ Fix: Always consider both time AND space. Sometimes you trade space for time (memoization).

❌ Mistake: Assuming nested loops are always O(n²).
✅ Fix: Check the loop bounds. for(i=0;i<n;i++) for(j=0;j<5;j++) is O(n), not O(n²).

❌ Mistake: Forgetting that in_array() is O(n).
✅ Fix: Use isset($arr[$key]) for O(1) lookups. Know your language's built-in complexities.

📝 Quick Quiz

Q1: What is the time complexity of Binary Search?

O(n) O(log n) O(n²) O(1)

Q2: Which Big O is the most efficient for large inputs?

O(1) O(n log n) O(n) O(log n)

Q3: What is the space complexity of an in-place algorithm?

O(n) O(1) O(n²) O(log n)

Q4: for($i=0;$i<$n;$i++) for($j=$i;$j<$n;$j++) — complexity?

O(n) O(n log n) O(n²) O(2ⁿ)

Q5: Big O describes the ______ case.

Best Average Worst (Upper Bound) All equally

📋 Complexity Cheat Sheet

O(1)	Constant	Array access, Hash lookup, Math ops
O(log n)	Logarithmic	Binary Search, Balanced BST ops
O(n)	Linear	Single loop, Linear search
O(n log n)	Linearithmic	Merge Sort, Heap Sort, Quick Sort (avg)
O(n²)	Quadratic	Bubble Sort, Nested loops
O(2ⁿ)	Exponential	Recursive Fibonacci, Subset generation
O(n!)	Factorial	Permutation generation, TSP brute force

Previous: Introduction Next: Arrays