Properties of Asymptotic Notations and common conjuctures

 

Properties of Asymptotic Notations

Introduction

Asymptotic notations are used to compare the growth rates of functions while ignoring constants and lower-order terms. They satisfy several useful mathematical properties that simplify the analysis of algorithms.

The major properties are

1. Reflexivity
2. Transitivity
3. Symmetry
4. Transpose Symmetry
5. Empty Set Property
6. Constant Multiplication
7. Addition Rule
8. Maximum Rule
9. Composition Property
10. Polynomial Property
11. Logarithm Property

---

1. Reflexivity Property

Every function is asymptotically bounded by itself.

$$f(n)=O(f(n))$$
$$f(n)=\Omega(f(n))$$
$$f(n)=\Theta(f(n))$$

Example

$$n^2=O(n^2)$$
$$n\log n=\Theta(n\log n)$$

---

2. Transitivity Property

If

$$f(n)=O(g(n))$$

and

$$g(n)=O(h(n))$$

then

$$f(n)=O(h(n))$$

Similarly,

$$f(n)=\Omega(g(n))$$

and

$$g(n)=\Omega(h(n))$$

implies

$$f(n)=\Omega(h(n))$$

Also,

$$f(n)=\Theta(g(n))$$

and

$$g(n)=\Theta(h(n))$$

implies

$$f(n)=\Theta(h(n))$$

Example

$$n=O(n^2)$$
$$n^2=O(n^3)$$

Therefore,

$$n=O(n^3)$$

---

3. Symmetry Property

Theta notation is symmetric.

If

$$f(n)=\Theta(g(n))$$

then

$$g(n)=\Theta(f(n))$$

Example

$$3n^2+5n=\Theta(n^2)$$

Therefore,

$$n^2=\Theta(3n^2+5n)$$

---

4. Transpose Symmetry

Big-O and Big-Omega are transpose of each other.

If

$$f(n)=O(g(n))$$

then

$$g(n)=\Omega(f(n))$$

Similarly,

If

$$f(n)=\Omega(g(n))$$

then

$$g(n)=O(f(n))$$

Example

$$n=O(n^2)$$

Hence,

$$n^2=\Omega(n)$$

---

5. Empty Set Property

No function can simultaneously satisfy

$$f(n)=o(f(n))$$

or

$$f(n)=\omega(f(n))$$

Hence,

$$o(f(n))\cap \omega(f(n))=\emptyset$$

---

6. Constant Multiplication Property

Multiplying by a positive constant does not change the asymptotic order.

If

$$f(n)=O(g(n))$$

then

$$cf(n)=O(cg(n))$$

where

$$c>0$$

Example

$$n=O(n^2)$$

Multiply by 5

$$5n=O(5n^2)$$

---

7. Addition Rule

If

$$f(n)=O(h(n))$$

and

$$g(n)=O(h(n))$$

then

$$f(n)+g(n)=O(h(n))$$

Example

$$3n+n^2$$

Since

$$3n=O(n^2)$$

Therefore

$$3n+n^2=O(n^2)$$

---

8. Maximum Rule

The larger-growing function dominates.

$$f(n)+g(n)=\Theta(\max(f(n),g(n)))$$

Example

$$n+n^2$$

Since

$$n^2>n$$

Therefore

$$n+n^2=\Theta(n^2)$$

Another example

$$n\log n+n$$

Result

$$=\Theta(n\log n)$$

---

9. Polynomial Property

If

$$f(n)=O(g(n))$$

then

$$(f(n))^k=O((g(n))^k)$$

for any positive constant

$$k$$

Example

$$n=O(n^2)$$

Squaring both sides

$$n^2=O(n^4)$$

---

10. Logarithm Property

If

$$f(n)=O(g(n))$$

and both functions are at least 1 for sufficiently large $n$,

then

$$\log f(n)=O(\log g(n))$$

Example

$$n=O(n^2)$$

Therefore

$$\log n=O(\log n^2)$$

Since

$$\log n^2=2\log n$$

---

11. Exponential Property

Unlike logarithms,

Big-O is not preserved under exponentiation.

Example

Suppose

$$n=O(n^2)$$

Then

$$2^n$$

is not

$$O(2^{n^2})$$

by simply applying the definition mechanically; exponential growth changes much more rapidly, so this requires separate analysis. In general, exponentiation is not a property that can be freely applied.

---

Common Conjectures 

The following table summarizes the conjectures from the CLRS exercise you posted.

Conjecture	True/False	Reason
$f=O(g)\Rightarrow g=O(f)$	❌ False	Example: $n=O(n^2)$, but $n^2\not=O(n)$
$f+g=\Theta(\min(f,g))$	❌ False	Dominated by the larger function, not the smaller.
$f=O(g)\Rightarrow \log f=O(\log g)$	✅ True	Logarithm is monotonic.
$f=O(g)\Rightarrow 2^f=O(2^g)$	✅ True	Since $f\le c\mathrm{g\; for\; some\; constant }$$c$, exponential preserves order up to constant multiples in the exponent for asymptotically positive functions under the exercise's assumptions.
$f=O(f^2)$	❌ False	Counterexample: $f(n)=1\mathrm{/}\mathrm{n,\; then }$$1/n\not=O(1/n^2)$
$f=O(g)\Rightarrow g=\Omega(f)$	✅ True	This is the transpose symmetry property.
$f(n)=\Theta(f(n/2))$	❌ False	Counterexample: $f(n)=2^n$, then $2^n$ is not $\mathrm{\Theta }(2^{n\mathrm{/}2})$
$f+o(f)=\Theta(f)$	✅ True	Lower-order terms do not change the asymptotic order.

---

Summary of Important Properties

Property	Formula
Reflexivity	$f(n)=O(f(n))=\mathrm{\Omega }(f(n))=\mathrm{\Theta }(f(n))$
Transitivity	$f=O(g),\;g=O(h)\Rightarrow f=O(h)$
Symmetry	$f=\Theta(g)\iff g=\Theta(f)$
Transpose Symmetry	$f=O(g)\iff g=\Omega(f)$
Constant Multiplication	$cf=\Theta(f)$ for $c>0$
Addition Rule	If $f,g=O(h)$, then $f+g=O(h)$
Maximum Rule	$f+g=\mathrm{\Theta }(\max (f,g))$
Polynomial Property	$f=O(g)\Rightarrow f^k=O(g^k)$
Logarithm Property	$f=O(g)\Rightarrow \log f=O(\log g)$ (for sufficiently large positive functions)
Lower-order Terms	$f+o(f)=\Theta(f)$