Suggest an edit

Improve this article

Refine the answer for “What is a function's "growth rate"?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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

1. 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).
2. 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.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts847 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.