What is a function's "growth rate"?

AlgorithmsJunior~3 min read

Short answer

A function's growth rate is how quickly the value of f(n) increases as n grows. In algorithm analysis it is described with asymptotic notations (O, Θ, Ω) to compare algorithms by the order of growth of time or memory on large inputs, ignoring constants and lower-order terms.

In detail

Definition and intuition

The growth rate of a function refers to its behavior as n → ∞. If for two functions f(n) and g(n), for sufficiently large n, the values of f grow no faster than some constant multiple of g, then f(n) is said to have a growth order no faster than g(n). In algorithms this lets you determine how running time or memory usage will scale as the input size n increases.

Why this matters in algorithms

Estimating scalability: how an algorithm behaves on large data.
Comparing alternatives: we choose the smaller growth order (for example, n log n is better than n^2).
Ignoring irrelevant factors: constants and lower powers do not affect the asymptotics.

Main asymptotic notations

O(g(n)) - upper bound (does not grow faster, up to a constant): f(n) ∈ O(g(n)) if ∃ c > 0, n0: f(n) ≤ c·g(n) for all n ≥ n0.
Ω(g(n)) - lower bound (does not grow slower, up to a constant): f(n) ∈ Ω(g(n)) if ∃ c > 0, n0: f(n) ≥ c·g(n) for all n ≥ n0.
Θ(g(n)) - exact order (both an upper and a lower bound at once): f(n) ∈ Θ(g(n)) if f ∈ O(g) and f ∈ Ω(g).
o(g(n)) - strictly slower (f/g → 0).
ω(g(n)) - strictly faster (f/g → ∞).

Important: the base of the logarithm does not affect the growth order (log_a n = (log_a b)·log_b n - a constant factor). Constant factors and lower-order additive terms are ignored as n → ∞.

How to compare two functions informally and formally

Limit method: consider L = lim n->∞ f(n)/g(n). If L = 0, then f ∈ o(g). If 0 < L < ∞, then f ∈ Θ(g). If L = ∞, then f ∈ ω(g).
Rules of thumb: compare polynomial powers by their exponents; n^a << n^b if a < b. Any polynomial << an exponential b^n. Logarithms grow slower than linear functions: log n << n.

Hierarchy of typical growth orders (from slow to fast)

Growth order	Short comment/example
1 (constant)	Accessing an array element by index
log n	Binary search
n	A single pass over an array
n log n	Comparison sorts (merge/quicksort on average)
n^2	Two nested loops (bubble sort)
n^3	Three nested loops (naive matrix multiplication)
2^n	Exhaustive search over subsets/solutions (exponential)
n!	Enumerating all permutations (grows extremely fast)

Code examples illustrating different growth rates

javascript

// O(1): constant time - does not depend on n
function getFirst(arr) {
  return arr[0];
}

// O(n): linear time - a single pass over the array
function sum(arr) {
  let s = 0;
  for (let i = 0; i < arr.length; i++) {
    s += arr[i];
  }
  return s;
}

// O(n log n): divide and conquer (example - merge sort)
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

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++]);
  }
  return res.concat(a.slice(i)).concat(b.slice(j));
}

// O(n^2): two nested loops - comparing every pair
function hasDuplicateQuadratic(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;
}

// Improving to O(n) with a hash table (a smaller growth rate)
function hasDuplicateLinear(arr) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

Practical interview tips

Speak in terms of input size n and use O/Θ/Ω notations.
Ignore constants and lower-order terms: 3n^2 + 10n + 100 is Θ(n^2).
Clarify the best/average/worst case and the data model used (for example, hash table access is amortized).
Distinguish theory from practice: for small n, an algorithm with a larger growth order can be faster due to small constants, but it will lose as n grows.

Common misconceptions and subtleties

Big-O is not exact timing, it is an asymptotic upper bound.
n log n can be larger than n^2 for very small n, but asymptotically n log n grows slower.
How the input is represented matters: numbers in binary form change the cost of operations logarithmically.
Asymptotics for memory are also a growth rate: for example, a data structure with Θ(n) memory.

Short Answer

Interview ready

Premium

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