Big-Oh Manipulation Rules and Typical Algorithm Growth Rates

Big-Oh notation (Big-O) is used to describe how an algorithm’s running time or space requirement scales with input size $n$.2 This section focuses on (1) algebraic “manipulation rules” you can apply safely to Big-O expressions and (2) the practical meaning of growth rates such as $O(\log n)$, $O(n\log n)$, and $O(2^n)$.

Key asymptotic concepts

• asymptotic upper bound
• dominant term
• lower-order terms

A useful mental model: when you simplify Big-Oh, you usually drop constants, drop smaller-order terms, and keep the highest-growth term—but you do so using rules that remain valid by definition.2

---

Footnotes

1. Big O notation - Wikipedia https://en.wikipedia.org/wiki/Big_O_notation - Formal definition using constants $c$ and $n_0$ (eventually bounded). ↩ ↩²

2. Asymptotic notation - Wikipedia https://en.wikipedia.org/wiki/Asymptotic_notation - Properties like dominance and behavior of common growth-rate classes. ↩ ↩²

Big-Oh definition (why the rules work)

By definition, $f(n)=O(g(n))$ means: there exist constants $c>0$ and $n_0$ such that for all $n\ge n_0$,
$f(n)\le c\cdot g(n).$
This “eventually bounded by a constant multiple” viewpoint is what makes algebraic simplifications safe (e.g., removing constants, ignoring lower-order terms, using max/dominance).

keyword Constant factors

If $f(n)\le c g(n)$, then multiplying $f$ by another constant or multiplying $g$ by a constant keeps it in the same asymptotic relationship (after adjusting $c$).

keyword Dominance

If $g_1(n)$ grows faster than $g_2(n)$ (e.g., $n^2$ dominates $n$), then $g_1(n)+g_2(n)$ is still $O(g_1(n))$ because eventually the larger term dominates.

---

Footnotes

1. Asymptotic notation - Wikipedia https://en.wikipedia.org/wiki/Asymptotic_notation - Properties like dominance and behavior of common growth-rate classes. ↩

Rules for manipulating Big-Oh expressions

These rules are widely used, and each aligns with the formal definition of Big-Oh as an eventually-bounded inequality.2

1) Basic scaling and constants

Let $f(n)=O(g(n))$ and $h(n)$ be any function with nonnegative growth for large $n$.

• Adding a constant:
  If $f(n)=O(g(n))$, then $f(n)+O(1)=O(g(n))$ (constants are lower-order than any unbounded $g$).
• Multiplying by a constant:
  If $f(n)=O(g(n))$, then $c\cdot f(n)=O(g(n))$ for constant $c>0$.
• Constant replacement:
  $O(c)=O(1)$ for constant $c>0$.

2) Sums: the maximum (dominant term) rule

• Sum of Big-Oh terms:
  $O(f(n)) + O(g(n)) = O(\max(f(n),g(n)))$.
  Intuition: for large $n$, one term eventually dominates the other, so the sum is bounded by a constant multiple of the larger term.2

Example:

• If $T(n)=O(n^2)+O(n)$, then $T(n)=O(n^2)$ because $n^2$ dominates $n$.

3) Products: multiply bounds

• Product rule:
  $O(f(n))\cdot O(g(n)) = O(f(n)g(n))$.
  Reason: if $f(n)\le c_1 g(n)$ and $g(n)\le c_2 h(n)$ (in bound form), then multiply inequalities and absorb constants into a new constant.

Example:

• If $T(n)=O(n)$ and $S(n)=O(\log n)$, then $T(n)\cdot S(n)=O(n\log n)$.

4) Powers: exponentiation changes growth class

• If $f(n)=O(g(n))$ and $k$ is a positive integer, then
  $(f(n))^k = O((g(n))^k)$
  (constants can again be absorbed into multiplicative factors).

Example:

• If $f(n)=O(n)$, then $(f(n))^2 = O(n^2)$.

5) Substitution / monotonic “reasonable” simplifications

Big-Oh manipulation typically assumes you are not doing invalid transformations like replacing a non-asymptotic step with a different function without justification. A safe pattern is:

• simplify within algebraic expressions using known identities, then apply the rules above (dominance, constants, max, products).

6) Common logarithm facts used in Big-Oh

These follow from logarithm identities:

• $\log(n^k)=k\log n$ (so $O(\log(n^k))=O(\log n)$ because $k$ is constant)
• $\log a + \log b = \log(ab)$ (then reclassify growth order)

[Callout]{type="tip" title="Pro Tip"} When multiple logs or polynomial terms exist, it’s often the largest-growth factor (like $n^2$ vs $\log n$) that determines Big-Oh after max/dominance simplification. [Callout]{type="warning" title="Common Pitfall"} Don’t assume $O(n)+O(n\log n)=O(n)$—the $n\log n$ term dominates $n$ for large $n$.

---

Footnotes

1. Big O notation - Wikipedia https://en.wikipedia.org/wiki/Big_O_notation - Formal definition using constants $c$ and $n_0$ (eventually bounded). ↩ ↩² ↩³ ↩⁴

2. Asymptotic notation - Wikipedia https://en.wikipedia.org/wiki/Asymptotic_notation - Properties like dominance and behavior of common growth-rate classes. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸

Typical growth rates (what they mean in practice)

Below are common growth-rate classes you’ll see when analyzing algorithms, along with intuition and how to compare them as $n\to\infty$.

Constant and logarithmic

• $O(1)$: constant time—bounded work independent of $n$.
• $O(\log n)$: work grows slowly; doubling $n$ adds only a constant number of iterations (common in binary search).
• $O(\log^k n)$: still polylogarithmic; treated as slower than any polynomial $n^a$ with $a>0$ in asymptotic comparisons.

Linear and near-linear

• $O(n)$: each element (or edge) is processed a constant number of times.
• $O(n\log n)$: typical for efficient comparison-based algorithms (e.g., mergesort-like patterns); the $\log n$ factor comes from divide-and-conquer or balanced recursion depth.2

Polynomial

• $O(n^2)$: quadratic—often from nested loops over $n$.
• $O(n^3)$: cubic—triple nesting or matrix-cubic transforms.
• General polynomial: $O(n^k)$ for constant $k$ grows much slower than exponential and factorial.

Exponential and factorial (infeasible at moderate sizes)

• $O(2^n)$: doubles the work with each extra element in the worst case—quickly becomes impractical.
• $O(n!)$: even faster than $2^n$; grows astronomically.

[Callout]{type="danger" title="Warning"} Exponential ($O(2^n)$) and factorial ($O(n!)$) algorithms typically only work for very small $n$. In contrast, polynomial-time algorithms scale much more gracefully as $n$ grows.

---

Footnotes

1. Asymptotic notation - Wikipedia https://en.wikipedia.org/wiki/Asymptotic_notation - Properties like dominance and behavior of common growth-rate classes. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Big O notation - Wikipedia https://en.wikipedia.org/wiki/Big_O_notation - Formal definition using constants $c$ and $n_0$ (eventually bounded). ↩

Growth-rate comparison: dominance ordering

A useful simplified ordering by “eventual speed” is:

$O(1) \prec O(\log n) \prec O(n) \prec O(n\log n) \prec O(n^2) \prec O(n^3) \prec O(2^n) \prec O(n!).$

This corresponds to the idea that for large $n$, faster-growing terms dominate sums and products under Big-Oh simplification rules.2

Mermaid: dominance intuition graph

---

Footnotes

1. Asymptotic notation - Wikipedia https://en.wikipedia.org/wiki/Asymptotic_notation - Properties like dominance and behavior of common growth-rate classes. ↩

2. Big O notation - Wikipedia https://en.wikipedia.org/wiki/Big_O_notation - Formal definition using constants $c$ and $n_0$ (eventually bounded). ↩