Big-O Addition Rule: Prove f1n+f2n=Og1n+g2n | AI Research

Big-O Addition Rule: Prove $f_1(n)+f_2(n)=O(g_1(n)+g_2(n))$

Verified Sources

Sep 14, 2026

We will prove a standard closure property of Big-O: if Big-O $f_1(n)=O(g_1(n))$ and $f_2(n)=O(g_2(n))$ , then

f_1(n)+f_2(n)=O(g_1(n)+g_2(n)).

This proof relies directly on the definition of Big-O and a simple inequality manipulation:

f_1(n)+f_2(n)\le c_1g_1(n)+c_2g_2(n)\le \max(c_1,c_2)\,(g_1(n)+g_2(n)).

To make the inequality step valid, we assume the usual conditions used with Big-O: $g_1(n)$ and $g_2(n)$ are nonnegative asymptotic functions for all $n\ge N$ (or at least that $g_1(n)+g_2(n)>0$ eventually), so $g_1(n)+g_2(n)$ can serve as an upper-bound scale. (These conditions are standard in algorithm analysis.)

Key terms used in this section: Big-O, asymptotic bound, eventually, nonnegative functions.

Big O notation (Wikipedia) https://en.wikipedia.org/wiki/Big_O_notation - Defines Big-O via constants and “for sufficiently large $n$ ”. ↩
Big O notation (math/CS context) https://en.wikipedia.org/wiki/Asymptotic_notations - Discusses formal definition and properties of asymptotic notation. ↩
Big O notation properties and manipulation https://en.wikipedia.org/wiki/Big_O_notation - Notes about algebraic manipulation and closure-like behaviors (with conditions). ↩

Big-O definition and basic proof patterns

Formal Big-O proof for the sum

1
Step 1
From $f_1(n)=O(g_1(n))$ , there exist constants $c_1>0$ and $N_1$ such that for all $n\ge N_1$ , $f_1(n)\le c_1 g_1(n)$ . Similarly, from $f_2(n)=O(g_2(n))$ , there exist $c_2>0$ and $N_2$ such that for all $n\ge N_2$ , $f_2(n)\le c_2 g_2(n)$ . Big-O
2
Step 2
Let $N=\max(N_1,N_2)$ . Then for all $n\ge N$ , both inequalities hold simultaneously.
3
Step 3
For all $n\ge N$ , $f_1(n)+f_2(n)\le c_1 g_1(n)+c_2 g_2(n).$
4
Step 4
Let $c=\max(c_1,c_2)$ . Then $c\ge c_1$ and $c\ge c_2$ , so $c_1 g_1(n)+c_2 g_2(n)\le c g_1(n)+c g_2(n)=c\,(g_1(n)+g_2(n)).$
5
Step 5
We have shown that for all $n\ge N$ , $f_1(n)+f_2(n)\le c\,(g_1(n)+g_2(n)).$ Therefore, $f_1(n)+f_2(n)=O(g_1(n)+g_2(n))$ by the definition of Big-O.

Pro Tip: Use $c=\max(c_1,c_2)$

When you have two Big-O bounds $f_1\le c_1 g_1$ and $f_2\le c_2 g_2$ , the cleanest way to combine them is to pick one constant that dominates both: $c=\max(c_1,c_2)$ .

Be careful about signs / eventual nonnegativity

The inequality $c_1 g_1(n)+c_2 g_2(n)\le c(g_1(n)+g_2(n))$ is straightforward if $g_1(n),g_2(n)\ge 0$ eventually. If signs can change, you must adapt the argument (e.g., use absolute values or ensure $g_1+g_2$ is eventually positive).

Why this works (intuition)

Big-O gives an eventual upper envelope: beyond some $N$ , each $f_i$ is no more than a constant multiple of its corresponding $g_i$ . Adding them preserves “upper envelope” behavior: the sum cannot grow faster than the sum of the envelopes (up to a constant factor).

This is a concrete instance of a more general closure property: if each term is bounded by a scaled reference function, then their combined expression is bounded by the combined reference function.

Key terms: closure property, upper bound, eventual inequality, constant factor.2

Big O notation (math/CS context) https://en.wikipedia.org/wiki/Asymptotic_notations - Discusses formal definition and properties of asymptotic notation. ↩
Big O notation properties and manipulation https://en.wikipedia.org/wiki/Big_O_notation - Notes about algebraic manipulation and closure-like behaviors (with conditions). ↩

Proof Roadmap (as you would teach it)

Unpack Big-O

Step A

Convert each $O$ statement into an explicit inequality with constants."

Choose a common $N$

Step B

Let $N=\max(N_1,N_2)$ so both inequalities hold together."

Add and bound again

Step C

Add the inequalities and upper-bound coefficients using $c=\max(c_1,c_2)$ ."

Apply the definition

Step D

Conclude $f_1+f_2=O(g_1+g_2)$ ."

Common pitfalls and extensions

How the bound behaves

Big-O of the sum is controlled by the combined envelopes $g_1+g_2$ .

Knowledge Check

Question 1 of 4

Q1Single choice

Suppose $f_1(n)=O(g_1(n))$ and $f_2(n)=O(g_2(n))$ . Which statement follows (under the standard eventual nonnegativity conditions)?

A: $f_1(n)+f_2(n)=O(g_1(n)+g_2(n))$

B: $f_1(n)+f_2(n)=O(g_1(n))$

C: $f_1(n)+f_2(n)=O(g_2(n))$

D: $f_1(n)+f_2(n)=\Theta(g_1(n)+g_2(n))$

Explore Related Topics

Primitive Recursiveness of the Sum Function $f(x,y)=x+y$

Complexity Analysis of a Divide-and-Conquer Recurrence

The course explains how to determine the asymptotic complexity of the divide‑and‑conquer recurrence  $T(n)=2T(n/4)+n^{2}\log n$ .

Identify parameters: $a=2$ , $b=4$ , $f(n)=n^{2}\log n$ .
Critical exponent $\log_b a=\log_4 2=0.5$ , so leaf cost grows as $n^{0.5}$ .
Since $f(n)=\Omega\!\big(n^{0.5+\epsilon}\big)$ for $\epsilon\le1.5$ , Case 3 of the Master Theorem applies.
Regularity condition holds with $c=1/8<1$ , confirming dominance of the root work.
Consequently $T(n)=\Theta(n^{2}\log n)$ , which is also derived via recursion‑tree and Akra‑Bazzi methods.

Cartesian Products Intersection When Sets Share $n$ Elements

Browse all research articles

Big-O Addition Rule: Prove f1(n)+f2(n)=O(g1(n)+g2(n))f_1(n)+f_2(n)=O(g_1(n)+g_2(n))f1​(n)+f2​(n)=O(g1​(n)+g2​(n))

Footnotes