Time and Space Complexity: A Developer's Complete Guide

In every coding interview, after you write your solution, the interviewer will ask: "What's the time and space complexity?" If you can't answer confidently, it's a red flag. Big O notation is the language of algorithm efficiency, and mastering it is non-negotiable.

What Is Big O Notation?

Big O describes how an algorithm's runtime or memory usage grows as the input size (n) increases. It focuses on the worst case and dominant term, ignoring constants and lower-order terms.

• O(2n + 5) simplifies to O(n)
• O(n² + n) simplifies to O(n²)
• O(500) simplifies to O(1)

Common Complexities (Best to Worst)

How to Analyze Your Code

Rule 1: Simple Loops = O(n)

// O(n) — single loop through array
function sum(arr: number[]): number {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total += arr[i]; // O(1) operation
  }
  return total;
}

Rule 2: Nested Loops = Multiply

// O(n²) — loop inside a loop
function hasDuplicate(arr: number[]): boolean {
  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;
}

Rule 3: Sequential Steps = Add

// O(n + m) — not O(n²)
function process(arr1: number[], arr2: number[]) {
  for (const x of arr1) { /* O(n) */ }
  for (const y of arr2) { /* O(m) */ }
}

Rule 4: Halving = O(log n)

// O(log n) — input halved each step
function binarySearch(arr: number[], target: number): number {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

Rule 5: Recursion — Draw the Tree

// O(2ⁿ) — each call branches into 2
function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// O(n) — with memoization, each value computed once
function fibMemo(n: number, memo = new Map()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

Space Complexity

Space complexity measures the additional memory your algorithm uses (excluding the input). Common sources:

• Variables — O(1)
• Arrays/hash maps — O(n) if they grow with input
• Recursion stack — O(depth) where depth is the maximum recursion depth
• 2D arrays — O(n × m)

Data Structure Complexity Cheat Sheet

Sorting Algorithm Complexities

Interview Tips for Complexity Analysis

• Always state both time and space — Don't wait to be asked about space
• Explain your reasoning — "This is O(n log n) because we sort the array first, then do a linear scan"
• Consider amortized complexity — Dynamic arrays have O(1) amortized insertion despite occasional O(n) resizing
• Watch for hidden loops — String concatenation in a loop, array.includes() inside a loop

Conclusion

Big O notation is a fundamental skill for every coding interview. Practice analyzing complexity as you solve problems — make it a habit, not an afterthought. This pairs directly with mastering LeetCode patterns and dynamic programming, where optimizing from brute force to optimal is the whole point.

Want to practice smarter? Try InterviewAlly free — get AI-powered assistance that helps you analyze and optimize your solutions in real-time.