Asymptotic Notation (O, Omega, Theta) Manipulation Rules

Intuition

Asymptotic classes obey simple algebra: a sum is governed by its largest term, and adding anything that is $O(f)$ to $f$ leaves you within a constant factor of $f$. But the bound $0 \le g(n)$ in the definitions only forces lower bounds when $f$ itself is bounded below — so identities involving roots or squares can fail for decaying functions.

Result / Method

Let $g(n)=O(f(n))$, i.e. $0\le g(n)\le c\,f(n)$. Then:

• Sum rule: $f(n)+O(f(n))\in\Theta(f(n))$, since $f(n)\le f(n)+g(n)\le(1+c)f(n)$.
• Dominant term: $\Theta(a(n)+b(n))=\Theta(\max(a(n),b(n)))$. So $f+f^2+\sqrt{f}=\Theta(f^2)$ once $f\to\infty$ — strictly bigger than $\Theta(f)$.
• Caution: $f(n)\in\Omega(\sqrt{f(n)})$ needs $\sqrt{f(n)}\ge c$, which fails if $f(n)\to 0$.

Worked example (q78)

With $f(n)$ only "a function of $n$" (not assumed $\to\infty$):

• I: $f(n)+O(f(n))\in\Theta(f(n))$ — always true (sandwich above).
• II: $f(n)\in\Omega(\sqrt{f(n)})$ — false: take $f(n)=1/n$, then $f/\sqrt{f}=1/\sqrt{n}\to 0$.
• III: $f(n)+f^2(n)+\sqrt{f(n)}\in\Theta(f(n))$ — false: take $f(n)=n$, sum is $\Theta(n^2)\neq\Theta(n)$.

Only I holds, so the count is 1.

Pitfall: Never silently assume $f(n)\to\infty$. "Obvious" identities like $f\in\Omega(\sqrt{f})$ hold for growing running times but break for a decaying $f$ such as $1/n$. Always probe with both a growing ($f=n$) and a shrinking ($f=1/n$) counterexample.