Big O Notation: Time & Space Complexity

Two Pointers Pattern (Converging & Symmetrical)

Master the converging two pointers technique to solve pair sum, palindrome verification, and partition problems in O(N) linear time.

1. Understanding Algorithm Scalability

When building scalable software, measuring execution speed in seconds is unreliable because hardware speeds vary. Big O Notation provides a mathematical framework to measure how an algorithm's runtime and memory requirements grow as the input size ($N$) approaches infinity.

2. The Big O Hierarchy (Fastest to Slowest)

Here is the asymptotic efficiency spectrum from best to worst:

O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(N!)
[Instant]   [Sub-linear]   [Linear]   [Log-linear]   [Quadratic]   [Exponential]

3. Visual Growth Rates

Operations
  ▲
  │                                     / O(2^N)
  │                                    /
  │                                   / O(N^2)
  │                                  /
  │                           . - '  O(N log N)
  │                    . - '
  │             . - '   O(N)
  │      . - '
  │  . -'       O(log N)
  │─────────────────────────── O(1)
  └───────────────────────────────────────► Input Size (N)

4. Analyzing Code Complexity

// O(1) Constant Time: Array index lookup
function getFirst(arr) {
  return arr[0];
}

// O(N) Linear Time: Single loop through array
function findMax(arr) {
  let max = -Infinity;
  for (const num of arr) {
    if (num > max) max = num;
  }
  return max;
}

// O(N^2) Quadratic Time: Nested loops (e.g. Pair comparison)
function printAllPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}

5. Common Mistakes

• Ignoring Space Complexity: Focusing only on runtime speed while ignoring auxiliary memory allocations (such as recursion call stacks or hash sets) can cause Out-Of-Memory (OOM) crashes in production.
• Assuming Fewer Lines Means Faster Code: Built-in methods like arr.includes() or str.slice() take $O(N)$ time under the hood even if written on one line.

6. Next Steps

Mastering Big O enables intelligent algorithmic trade-offs. Next, let's explore Dynamic Arrays and Amortized Resizing!