What does "algorithm complexity" mean?

AlgorithmsJunior~3 min read

Short answer

Algorithm complexity is an estimate of how resource costs (time and memory) change as the input size n grows. Most often we talk about time complexity and space complexity in asymptotic notations (O, Θ, Ω), usually for the worst case. We ignore constants and lower orders so algorithms can be compared independently of hardware and implementation details.

In detail

What "complexity" means

Time complexity: how the number of elementary operations grows as n increases.
Space complexity: how the amount of extra memory grows, not counting input/output.
Cases: worst-case, average-case, best-case. In an interview, the worst case is assumed by default unless stated otherwise.

Notations

O (Big-O): upper bound - how fast time/memory can grow in the worst case.
Θ (Theta): exact asymptotics - upper and lower bounds coincide by order.
Ω (Omega): lower bound - how fast it grows at minimum.
Amortized complexity: the average cost of one operation across a sequence (for example, push on a dynamic array).

Rules for a quick estimate

A sequence of independent blocks: add them up (take the dominant order).
Nested loops: multiply the iteration counts.
Conditional branches: take the worst one by complexity.
Splitting the task in half (like binary search): logarithm O(log n).
Recursions with splitting (for example, sorting): use recurrence relations; these often give O(n log n).
Drop constants and lower orders: O(3n + 10) → O(n).

Code examples with a breakdown

A linear pass - O(n) time, O(1) memory:

javascript

function sum(arr) {
  let s = 0;                // O(1)
  for (let i = 0; i < arr.length; i++) { // n times
    s += arr[i];            // O(1) * n
  }
  return s;                 // O(1)
}
// Total: O(n) time, O(1) extra memory

Nested loops - O(n^2):

javascript

function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {        // n
    for (let j = i + 1; j < arr.length; j++) {  // ~n/2 on average
      if (arr[i] === arr[j]) return true;       // O(1)
    }
  }
  return false;
}
// Total: O(n^2) time, O(1) memory

Logarithmic complexity (binary search) - O(log n):

javascript

function binarySearch(sortedArr, target) {
  let l = 0, r = sortedArr.length - 1;
  while (l <= r) {                 // halve the range on each step
    const mid = (l + r) >> 1;
    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) l = mid + 1; else r = mid - 1;
  }
  return -1;
}
// O(log n) time, O(1) memory

Sorting via splitting (merge sort) - O(n log n) time, O(n) memory:

javascript

function mergeSort(a) {
  if (a.length <= 1) return a;
  const mid = a.length >> 1;
  const left = mergeSort(a.slice(0, mid));   // T(n/2)
  const right = mergeSort(a.slice(mid));     // T(n/2)
  return merge(left, right);                 // O(n)
}

function merge(l, r) {
  const res = [];
  let i = 0, j = 0;
  while (i < l.length && j < r.length) {
    if (l[i] <= r[j]) res.push(l[i++]); else res.push(r[j++]);
  }
  return res.concat(l.slice(i)).concat(r.slice(j));
}
// Recurrence relation: T(n) = 2T(n/2) + O(n) => O(n log n)

Amortized complexity illustrated by push on a dynamic array: most operations are O(1), occasionally - rare resizes cost O(n), but on average - O(1):

javascript

const a = [];
for (let i = 0; i < 1e6; i++) {
  a.push(i); // usually O(1); on a rare buffer growth - more expensive, but amortized O(1)
}
// In JavaScript array size grows automatically; the model is the same as for dynamic arrays

Complexity classes and examples

Class	What it means	Example
O(1)	Constant	Access by index in an array
O(log n)	Logarithmic	Binary search
O(n)	Linear	A pass over an array
O(n log n)	Linearithmic	Merge sort, Quick sort (on average)
O(n^2)	Quadratic	Two nested loops over n
O(2^n)	Exponential	Exhaustive search over subsets
O(n!)	Factorial	Enumerating all permutations

Memory: how to count it

Extra data structures: arrays, maps, the recursion stack.
Input and output are usually not counted (unless stated otherwise).
In-place algorithms: O(1) extra memory, but check the call stack for recursion.

Frequent traps in interviews

Talking only about the best case instead of the worst case.
Ignoring memory or the recursive stack.
Missing constants where they matter in practice (for example, choosing a sort for small n).
Not accounting for the input distribution (for example, being nearly sorted).

How to answer briefly and in a structured way

Define what n is (array length, number of nodes, range of values, etc.).
Clarify the case (worst/average/best) and memory constraints.
Evaluate blocks: loop/nesting/branches/recursion. Explain the rules (add/multiply/take the maximum).
State the result: time and memory, and an amortized estimate if needed.
Briefly note the trade-offs (speed vs memory, stability, code simplicity).

Mini case: evaluating code with a conditional exit

javascript

function findFirstGreater(arr, x) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > x) return i; // early exit
  }
  return -1;
}
// Worst case: O(n) (found nothing)
// Best case: O(1) (the first element matched)
// Average: depends on the distribution; often ~O(n)

Summary: "algorithm complexity" is a formal way to talk about scalability in time and memory relative to the input size. In an interview it is important to be able to name the notation, the case, the assumptions about the input, and to justify the estimate.

Short Answer

Interview ready

Premium

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