How can algorithm complexity be determined?

JavaScript~4 min read

Algorithm complexity measures how an algorithm's runtime or memory use scales with input size, expressed in Big O notation as a worst-case upper bound.

Theory

TL;DR

Big O counts how operations grow as n grows, not how fast your machine runs code.
Find the dominant operation: the deepest loop or heaviest recursion. Everything else is noise.
If input doubles and time quadruples, that's O(n²). If time doubles, that's O(n).
Drop constants: 3n + 5 becomes O(n). The loop dominates when n is large.
Two separate loops over the same array = O(n), not O(2n).

Quick example

javascript

// O(1) - constant: doesn't care about array size
function getFirst(arr) {
  return arr[0]; // always 1 operation, whether arr has 3 or 3 million items
}

// O(n) - linear: one loop, one pass
function sum(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) { // n steps
    total += arr[i];
  }
  return total;
}

// O(n²) - quadratic: loop inside a loop
function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {       // n
    for (let j = i + 1; j < arr.length; j++) { // up to n
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

The rule: count the nesting level of your loops. One loop = O(n). Loop inside a loop = O(n²). Each level multiplies.

Key difference: operations vs lines of code

A common confusion is treating each line of code as "one operation." That only works for fixed-index access like arr[0]. The moment your code depends on n, the count changes. arr[i] inside a loop runs n times, not once. Track what scales with input size.

How to analyze code step by step

Read your code from the inside out:

Find the innermost operation (an assignment, comparison, or array access).
Count how many times it runs relative to n.
One surrounding loop = O(n). Two nested loops = O(n²).
For recursion, count the depth of the call tree. A function calling itself twice per call gives O(2^n) without memoization.
Keep the dominant term only. O(n² + n) simplifies to O(n²).

When to use each class

Fixed-size input (under 100 items): O(n²) is fine. You won't notice.
User data (1K to 1M items): aim for O(n log n) or better. O(n²) will lag.
Real-time (games, UI interactions): stick to O(1) or O(log n).
Sorting: the built-in array.sort() is O(n log n).

Complexity classes at a glance

Complexity	n=10	n=100	Example
O(1)	1	1	`obj.key`, `arr[0]`
O(log n)	3-4	7	Binary search
O(n)	10	100	`array.filter()`
O(n log n)	~33	~664	`array.sort()`
O(n²)	100	10,000	Nested loops, bubble sort
O(2^n)	1,024	~10^30	Naive recursive Fibonacci

O(n²) at n=100 means 10,000 operations. At n=1000, it's a million. That's the gap that crashes production.

Common mistakes

Mistake 1: Thinking chained .filter().map() is O(n²)

javascript

// O(2n) = O(n) - two separate passes, still linear
const result = arr.filter(x => x > 0).map(x => x * 2);

Two loops over the same array add, they don't multiply. O(n + n) = O(2n) = O(n).

Mistake 2: Hidden nested built-ins

javascript

// O(n²) hiding behind clean syntax
arr.map(a => others.includes(a)); // .includes() is O(n) inside an O(n) map

Fix: build a Set first. const set = new Set(others); arr.map(a => set.has(a)); drops it to O(n). Most production .includes() bugs I've seen come from exactly this pattern.

Mistake 3: Naive recursion

javascript

// O(2^n) - freezes a browser tab at n=50
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // two calls per level = exponential tree
}

// O(n) with memoization
const memo = new Map();
function fibMemo(n) {
  if (memo.has(n)) return memo.get(n);
  if (n <= 1) return n;
  const res = fibMemo(n - 1) + fibMemo(n - 2);
  memo.set(n, res);
  return res;
}
console.log(fibMemo(100)); // instant

fib(40) technically completes but takes noticeable time. fib(50) will freeze the tab. The call tree branches twice at every node.

Mistake 4: Treating space complexity as an afterthought

javascript

function dup(arr) {
  return arr.concat(arr); // O(n) extra space, easy to miss
}

If arr has 1M items, you just allocated 2M in memory. Space complexity counts auxiliary allocations, not just time.

Real-world usage

React: useMemo prevents re-running O(n) sorts on every render - const sorted = useMemo(() => users.sort((a, b) => a.age - b.age), [users]).
Express: scanning a DB array for a matching user is O(n). Add a database index and it becomes O(log n).
Node.js: readFileSync is O(n) where n is file size. Use streams for large files.
Set vs array: arr.includes(item) is O(n). set.has(item) is O(1).

Follow-up questions

Q: What's the difference between O(n) and Θ(n)?
A: O(n) is an upper bound: the algorithm runs in at most kn operations. Θ(n) is a tight bound: both upper and lower bounds are proportional to n. Interviewers usually mean Θ when they say O, but seniors know the difference.

Q: What is the time complexity of this loop?

javascript

for (let i = 0; i < n; i++)
  for (let j = i; j < n; j++) sum += arr[i][j];

A: O(n²/2) = O(n²). The inner loop shrinks each iteration, but it's still a triangular traversal. Constants drop.

Q: What is the space complexity of quicksort?
A: O(log n) average case from recursion stack depth, O(n) worst case. Merge sort is always O(n) because it allocates a temporary array.

Q: array.includes(item) - what's the Big O?
A: O(n). It scans from index 0 every time. Use Map or Set for O(1) lookup.

Examples

Finding the maximum value

javascript

function findMax(numbers) {
  let max = numbers[0]; // O(1) - one assignment

  for (let i = 1; i < numbers.length; i++) { // O(n) - one full pass
    if (numbers[i] > max) max = numbers[i];
  }

  return max; // total complexity: O(n)
}

console.log(findMax([3, 7, 1, 9, 4])); // 9

The loop runs n - 1 times. Drop the constant: O(n). The function's complexity is determined by its most expensive operation. Here that's the single pass through the array.

Filtering a list with set-based lookups

javascript

const users = [{ id: 1, name: "Alice" }, { id: 2, name: "Bob" }, { id: 3, name: "Carol" }];
const blocked = [1, 5, 7];

// O(n * m) - for each user, scans the entire blocked list
const slow = users.filter(u => blocked.includes(u.id));

// O(n + m) - Set builds once, each lookup is O(1)
const blockedSet = new Set(blocked);
const fast = users.filter(u => !blockedSet.has(u.id));

console.log(fast); // [{ id: 2, name: "Bob" }, { id: 3, name: "Carol" }]

The difference is invisible with 3 users and 3 blocked IDs. With 10,000 users and 1,000 blocked IDs, the first version does 10 million comparisons. The second does 11,000.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.

Finished reading?