What does an "order-of-growth estimate" mean?

AlgorithmsJunior~4 min read

Short answer

An order-of-growth estimate is a way to describe how an algorithm's running time or memory usage increases as the input size n grows. It usually uses asymptotic O(·) notation: constants and lower-order terms are dropped, leaving the dominant contribution, for example O(n), O(n log n), O(n²).

Detailed explanation

What order of growth is and why it is needed

Order of growth describes how fast an algorithm's resources (time, memory) grow as the input size n increases. It lets you compare algorithms abstracting away from the specific machine, language, and optimizations, focusing on what matters most for large n.

It focuses on the dominant term: O(n + 5) → O(n).
It ignores constant factors: O(3n) → O(n).

The main idea: how the scale of time/memory changes as n grows by a factor, not the exact number of operations.

Main notations

O(g(n)) - an upper bound by order of growth: the algorithm is no worse than g(n), up to a constant, for large n.
Θ(g(n)) - exact by order of growth: both the upper and lower bounds coincide (asymptotically the same growth).
Ω(g(n)) - a lower bound: the algorithm is no better than g(n) by order of growth.
o(g(n)) - grows strictly slower than g(n). ω(g(n)) - grows strictly faster.
Amortized complexity - the average cost of an operation over a long sequence of calls (important for dynamic data structures).

What exactly is being estimated

Time: the number of elementary steps (iterations, comparisons, assignments, etc.).
Memory: extra memory beyond the input data (recursion stack, temporary structures).
Case: worst-case, average-case, best-case. In interviews, the worst case is assumed by default unless stated otherwise.

Practical rules for estimating code

Sequential sections of code: take the maximum of the complexities, not the sum, when they depend on the same n (O(n) + O(n²) → O(n²)).
A single loop over n elements → O(n). Loop steps with a dividing/multiplying index (i *= 2) → O(log n).
Nested independent loops → multiply (outer n, inner n → O(n²)). Sequential loops over the same array → O(n) + O(n) → O(n).
Conditional branches: take the maximum of the branches by order of growth (the worst-case scenario).
Recursion: estimate the number of calls and the work per level; the divide-and-conquer rule often helps (T(n) ≈ a·T(n/b) + f(n)). Examples: binary search → O(log n), merge sort → O(n log n).
Define what n is: array length, number of nodes in a tree, number of vertices/edges in a graph, and so on. The estimate depends on this.

Code examples and their order of growth (JS)

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

function sum(arr) {
  let s = 0;
  for (let i = 0; i < arr.length; i++) {
    s += arr[i];
  }
  return s;
}

Nested loops - O(n²) time:

function hasDuplicates(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;
}

Binary search over a sorted array - O(log n) time:

function binarySearch(arr, x) {
  let l = 0, r = arr.length - 1;
  while (l <= r) {
    const m = (l + r) >> 1;
    if (arr[m] === x) return m;
    if (arr[m] < x) l = m + 1; else r = m - 1;
  }
  return -1;
}

Merging two sorted arrays - O(n + m) time, O(n + m) memory (for the result):

function merge(a, b) {
  const res = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) res.push(a[i++]);
    else res.push(b[j++]);
  }
  while (i < a.length) res.push(a[i++]);
  while (j < b.length) res.push(b[j++]);
  return res;
}

Merge sort - O(n log n) time, O(n) extra memory:

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  // Merging - as in the example above
  const res = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) res.push(left[i++]);
    else res.push(right[j++]);
  }
  while (i < left.length) res.push(left[i++]);
  while (j < right.length) res.push(right[j++]);
  return res;
}

Amortized complexity of push on a dynamic array - O(1) on average, sometimes O(n) on a rare resize:

class DynArray {
  constructor() {
    this.a = new Array(1);
    this.n = 0;
  }
  push(x) {
    if (this.n === this.a.length) {
      const b = new Array(this.a.length * 2);
      for (let i = 0; i < this.n; i++) b[i] = this.a[i];
      this.a = b; // a rare but expensive operation: O(n)
    }
    this.a[this.n++] = x; // usually O(1)
  }
}

Typical orders of growth and intuition

O(1) - constant: access by index in an array, push to the end of a dynamic array (amortized).
O(log n) - halving: binary search, operations in balanced search trees.
O(n) - a linear pass: checking a condition for every element of an array/list/node.
O(n log n) - comparison sorts, many divide-and-conquer algorithms (merging, quicksort on average).
O(n²) - double nested loops: comparing everyone with everyone, naive DP algorithms without optimizations.
O(2^n), O(n!) - exhaustive search, combinatorial problems without optimizations/pruning.

Frequent mistakes and subtleties

Confusion about the definition of n: for graphs it is important to distinguish |V| (vertices) from |E| (edges); for strings - the length in characters; for numbers - the number of bits, not the value of the number.
Ignoring memory: recursive algorithms often need O(depth) stack; some sorting methods need O(n) extra memory.
Taking constants too literally: the asymptotics ignores constants, but for small n they can matter in practice. In an interview, discuss the trade-offs.

How to answer in an interview

State what you take as n (the input size) and which case you are considering (usually the worst).
Break the code into blocks: sequential parts, loops, branches, recursion; apply the addition/multiplication/maximum rules.
State the time and space complexity; give the amortized one if needed.
Compare alternatives and point out the bottleneck (for example, "the bottleneck is a nested O(n²) loop").

Short Answer

Interview ready

Premium

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