How to Analyze Time Complexity of Any Algorithm

Time complexity measures how the number of operations grows as the input size ngrows. You don’t count exact operations — you count how that count scales. The question to ask for every piece of code is: “if I double the input, how does the work change?”

A loop that runs once per element does one unit of work per element, so the total work scales linearly with the input:

function sum(nums) {
  let total = 0;
  for (let i = 0; i < nums.length; i++) {
    total += nums[i]; // O(1) work, done n times
  }
  return total;
}
// Time: O(n)

It doesn’t matter what happens inside the loop body, as long as it’s constant-time work — the loop runs n times, so the function is O(n).

When a loop runs inside another loop, the work for the inner loop happens once for every iteration of the outer loop. Multiply their complexities together:

function hasDuplicatePair(nums) {
  for (let i = 0; i < nums.length; i++) {       // n iterations
    for (let j = 0; j < nums.length; j++) {     // n iterations, for each i
      if (i !== j && nums[i] === nums[j]) return true;
    }
  }
  return false;
}
// Time: O(n) * O(n) = O(n²)

This generalizes: three nested loops over the same input is O(n³), and so on. The rule is multiply the iteration counts, not add them — the inner loop restarts fully for every pass of the outer loop.

For recursive functions, first figure out how many times the function calls itself, then how much work each call does on its own (excluding the recursive calls). A recursive sum that makes one call per element and does O(1) work per call is still O(n):

function sum(nums, i = 0) {
  if (i >= nums.length) return 0;
  return nums[i] + sum(nums, i + 1); // one recursive call, O(1) own work
}
// Time: O(n) — n calls, O(1) work each

But a recursive function that makes two calls per invocation — like the naive Fibonacci implementation — branches exponentially:

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // two recursive calls
}
// Time: O(2ⁿ) — the call tree doubles at every level

Adding memoization (caching each result the first time it’s computed) collapses this back down to O(n), because each distinct subproblem is only ever solved once.

O(log n) shows up whenever an algorithm discards a constant fraction of the remaining input at each step, rather than a constant amount. Binary search is the canonical example — it halves the search space every iteration:

function binarySearch(sortedNums, target) {
  let low = 0, high = sortedNums.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (sortedNums[mid] === target) return mid;
    if (sortedNums[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}
// Time: O(log n) — the search space halves each iteration

To find how many halvings it takes to shrink n down to 1, you’re asking “2 to what power equals n?” — that’s exactly what log₂(n) means. For n = 1,024, that’s only 10 iterations.

Big-O describes behavior as n gets large, so you drop constants and keep only the fastest-growing term. If a function does one loop of n, then a nested loop of n², the total operation count is n + n², but for large n the n² term dominates completely:

function process(nums) {
  for (const x of nums) { /* O(n) */ }

  for (const x of nums) {
    for (const y of nums) { /* O(n²) */ }
  }
}
// Total: O(n) + O(n²) → simplify to O(n²)

• Drop constants: O(3n) simplifies to O(n) — a loop that runs three separate times over the input is still linear.
• Drop lower-order terms: O(n² + n) simplifies to O(n²) — the smaller term becomes irrelevant as n grows.
• Sequential blocks add, nested blocks multiply: two separate loops back-to-back add their complexities; a loop inside a loop multiplies them.

Walk through this function using the rules above:

function example(nums) {
  console.log(nums[0]);              // O(1)

  for (const x of nums) {            // O(n)
    console.log(x);
  }

  for (const x of nums) {            // O(n) outer
    for (const y of nums) {          // O(n) inner, multiplied
      console.log(x, y);
    }
  }
}

Three blocks, run sequentially: O(1) + O(n) + O(n²). Add them, then keep only the dominant term:

Final answer: O(n²)

See these rules applied to real algorithms — binary search is a worked example of logarithmic behavior, merge sort is a worked example of the multiply-per-level reasoning behind O(n log n), and quicksort shows how the same reasoning explains a worst-case blowup to O(n²):

• Binary Search — O(log n) explained
• Merge Sort — O(n log n) explained
• Quicksort — best, average, and O(n²) worst case explained

This guide covers time complexity — for the memory side of the same analysis, see Space Complexity Explained. Keep the full table of complexity classes handy while you practice, and check back here as more algorithm breakdowns (dynamic programming) are published.

Once you’re comfortable deriving Big-O, learn how it relates to Big-Omega and Big-Theta in Big-O vs. Big-Theta vs. Big-Omega, or see quick answers to common questions in the FAQ.

← Back to the Big-O Cheat Sheet