Time & Space Complexity

Understanding complexity analysis is essential for writing efficient code. It helps you predict how your algorithm will perform as data grows.

What is Big O Notation?

Key principle: We care about the worst case and how it scales, not the exact number of operations.

Common Time Complexities

O(1) - Constant Time

The operation takes the same time regardless of input size.

// Array access by index
function getFirst(arr) {
  return arr[0];  // Always 1 operation
}

O(log n) - Logarithmic Time

The problem size is halved with each step. Very efficient!

// Binary search
function binarySearch(arr, target) {
  let left = 0, 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;
}

O(n) - Linear Time

Time grows proportionally with input size.

// Find maximum value
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

O(n²) - Quadratic Time

Nested iterations - gets slow quickly!

// Check for duplicates (naive)
function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

Complexity Comparison Table

Space Complexity

Space complexity measures memory usage as input grows.

Rules for Calculating Big O

• Drop constants: O(2n) → O(n)
• Drop lower terms: O(n² + n) → O(n²)
• Consider worst case: Array search might find element first or last
• Different inputs = different variables: O(n + m), not O(2n)

Quick Reference

What's Next?

Now that you understand complexity, let's dive into specific data structures starting with Arrays - the most fundamental data structure.