Suggest an editImprove this articleRefine the answer for “What does an "order-of-growth estimate" mean?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)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²). **Key point:** the main idea is how the scale of time/memory changes as n grows by a factor, not the exact number of operations.Shown above the full answer for quick recall.Answer (EN)Image## 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 1. State what you take as n (the input size) and which case you are considering (usually the worst). 2. Break the code into blocks: sequential parts, loops, branches, recursion; apply the addition/multiplication/maximum rules. 3. State the time and space complexity; give the amortized one if needed. 4. Compare alternatives and point out the bottleneck (for example, "the bottleneck is a nested O(n²) loop").For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.